Математика в этом алгоритме поиска подстроки анаграммы - PullRequest
Новая
       13

Математика в этом алгоритме поиска подстроки анаграммы

0 голосов
/ 16 января 2019

В следующем коде: 

function sherlockAndAnagrams(s) {
var pairs = 0;
var subStrings = {};

//find all substrings of our string, count them in a hash
for(var i = 0; i < s.length; i++){
    for(var j = i; j < s.length; j++){
        let tempSubString = s.substring(i, j+1).split("").sort().join("");
        if(subStrings[tempSubString]){
            subStrings[tempSubString] +=1;
        }else{
            subStrings[tempSubString] = 1;
        }
    }
}

//****ATTENTION******
for(var keys in subStrings){
    if(subStrings[keys] > 1){
    let temp = (subStrings[keys])*(subStrings[keys]-1)/2;
       pairs += temp;
   }
}
return pairs;
}

Я не уверен, как работает математика этой формулы:

subString [keys]) * (subString [keys] -1) / 2

Предполагая, что s = "kkkk", будет 6 анаграмм "k" s

Может кто-нибудь объяснить это?

Кроме того, этот вид говорит мне, чтоЯ могу быть немного не хватает определенного типа математики.Если бы вы могли посоветовать мне хороший материал для изучения математики таким образом, я был бы признателен за это!

1 Ответ

0 голосов
/ 16 января 2019

Логика следующая: у вас есть n слова, которые являются анаграммами друг друга. Сколько пар анаграмм вы можете выбрать оттуда? Это простой комбинаторный вопрос с известным ответом: биноминальный коэффициент из (n,2), который равен n*(n-1)/2.

Логика состоит в том, что если вы посчитаете все анаграммы, первую анаграмму вы можете выбрать n способами, вторую - n-1 способами, но каждая анаграмма будет рассматриваться дважды: один раз как ab=ba и другой раз как ba=ab

...