12

(私は JavaScript のコンテキストでこれを書いていますが、どの言語でもアルゴリズム的に正しい答えを受け入れます)

大文字と小文字を区別せずに、部分文字列が他の要素のいずれにも含まれていない文字列の配列内の各要素の最短部分文字列をどのように見つけますか?

次のような入力配列があるとします。

var names = ["Anne", "Anthony", "LouAnn", "Kant", "Louise", "ark"];

出力は次のようになります。

var uniqueNames = ["ne", "h", "ua", "ka", "i", "r"];

私の目的のために、別の要素内に完全に含まれる要素はないと安全に想定できます。

私の考え:
おそらく、次のように力ずくで実行できるように思われます。

var names = ["Anne", "Anthony", "LouAnn", "Kant", "Louise", "ark"];
var uniqueNames = [], nameInd, windowSize, substrInd, substr, otherNameInd, foundMatch;
// For each name
for (nameInd = 0; nameInd < names.length; nameInd++)
{
    var name = names[nameInd];
    // For each possible substring length
    windowLoop:
    for (windowSize = 1; windowSize <= name.length; windowSize++)
    {
        // For each starting index of a substring
        for (substrInd = 0; substrInd <= name.length-windowSize; substrInd++)
        {
            substr = name.substring(substrInd,substrInd+windowSize).toLowerCase();
            foundMatch = false;
            // For each other name
            for (otherNameInd = 0; otherNameInd < names.length; otherNameInd++)
            {
                if (nameInd != otherNameInd && names[otherNameInd].toLowerCase().indexOf(substr) > -1)
                {
                    foundMatch = true;
                    break;
                }
            }

            if (!foundMatch)
            {
                // This substr works!
                uniqueNames[nameInd] = substr;
                break windowLoop;
            }
        }
    }
}

しかし、トライ/プレフィックスツリー、サフィックス配列、またはそのような興味深いものを使用した、より洗練されたソリューションがあると想像する必要があります。

編集：これは、選択された回答がJavaScriptでプログラム的にとる形式だと思います：

var names = ["Anne", "Anthony", "LouAnn", "Kant", "Louise", "ark"];
var uniqueNames = [], permutations = {}, permutation, nameInd, windowSize, substrInd, substr;

// For each name
for (nameInd = 0; nameInd < names.length; nameInd++)
{
    var name = names[nameInd];
    // For each possible substring length
    windowLoop:
    for (windowSize = 1; windowSize <= name.length; windowSize++)
    {
        // For each starting index of a substring
        for (substrInd = 0; substrInd <= name.length-windowSize; substrInd++)
        {
            substr = name.substring(substrInd,substrInd+windowSize).toLowerCase();
            permutations[substr] = (typeof permutations[substr] === "undefined")?nameInd:-1;
        }
    }
}

for (substr in permutations)
{
    permutation = permutations[substr];
    if (permutation !== -1 && ((typeof uniqueNames[permutation] === "string" && substr.length < uniqueNames[permutation].length) || typeof uniqueNames[permutation] === "undefined"))
    {
        uniqueNames[permutation] = substr;
    }
}
4

4 に答える 4

2

は文字列Nの数であり、文字列Lの最大長です。あなたはN*L*L*N反復までやっています。

1回の反復を余分なメモリと交換することで、少しだけ改善できます。可能な部分文字列の長さ (L反復) ごとに、

  • 各名前でその長さのすべての部分文字列を列挙し ( N*L)、名前のインデックスと共にハッシュテーブルに格納します ( 1)。この部分文字列のインデックスが既に存在する場合、それが機能しないことがわかっている場合は、 index を などの特別な値に置き換えます-1。

  • ハッシュテーブルをたどり、インデックスがそうでない部分文字列を拾います-1—それは対応するインデックスの答えですが、その名前が以前の反復からのより短い答えをまだ持っていない場合にのみそれらを使用します

部分文字列をコピーするのではなく、参照を既存の文字列に戻すことで、メモリ使用量を大幅に削減できます。

于 2012-07-01T08:52:55.713 に答える
-1 
   for(String s : strArr) { //O(n)
      //Assume the given string as shortest and override with shortest
       result.put(s, s);   
       for(int i = 0; i < s.length(); i++) { // O(m)              
          for (int j = i + 1; j <=s.length(); j++) {
               String subStr = s.substring(i, j);
               boolean isValid = true;
               for(String str2: strArr) { // O(n)
                   if(str2.equals(s)) // Same string cannot be a substring
                     continue;
                     
                    if(str2.contains(subStr)) {
                        isValid = false;
                        break;
                    }
               }

               if(isValid && subStr.length() < result.get(s).length()) 
                   result.put(s, subStr);
           }
        } 
   } 
    
   return result;
于 2021-05-23T16:57:39.200 に答える