一個算法來判斷從列表中辨別出單詞需要多少個不同的主要字符？

所以，如果你有50個單詞的列表，你想看到一個讀者必須看看有多深成一個字能算所有的獨特的話，你會如何去這樣做？一個算法來判斷從列表中辨別出單詞需要多少個不同的主要字符？

基本上，我想裝成字符數組，一個接一個，然後比較它們。雖然有很多字符和很多數組可供比較。我想知道最有效的方法是什麼，如果已經有一種高效的方法？

我試圖使用JavaScript，現在。

var words = [sort(prompt("Please, insert the word list", "default value in the text field"););]; 
var encr_int: Number=0; 
for (i=0, j=0, maxdif=0; j < word.length; i++) { 
    if(word[j].text.charAt(i) == word[j+1].text.charAt(i) AND i > maxdif) { 
     maxdif = i; 
    } 
    else if(word[j].text.charAt(i) != word[j+1].text.charAt(i) { 
     j+=1; 
    } 
    else if(word[j].text.charAt(i) == "") { 
     i = 0; 
    } 
} 
document.write(maxdif);

以上是我根據第一個答案編寫程序的努力。

來源

2011-11-25 Wolfpack' 08

這是我的嘗試，如果你感興趣也許：http://jsfiddle.net/sBcZa/3/。（這是瀏覽器JavaScript;我不確定你的'：數字'和'AND'是什麼意思。） – pimvdb

@pimvdb對不起。我仍然在學習Javacript。我在一本名爲Eloquent Javascript的書的第6章中，我可能需要再讀兩遍或三遍以上的全書。「數字」是從一個粘貼結轉的東西。 –

這是否使用了trie或者是否使用了Pointy的解決方案？ –

排序列表，然後遍歷它，每一個字與字以後比較。比較一個例程，告訴你在找到差異之前必須檢查多少個字符。隨時跟蹤最大「深度」。

編輯 —一個函數來告訴你的基於主角兩個字「相似性」：

function similarity(w1, w2) { 
    var i, l = Math.min(w1.length, w2.length); 

    for (i = 0; i < l; ++i) 
    if (w1[i] !== w2[i]) break; 

    return i; 
}

來源

2011-11-25 10:54:18 Pointy

好的，讓我試着寫下它。 –

你說「算法」，所以我不想放棄太多:-) – Pointy

很酷。謝謝。對此嘗試有任何想法？ :) –

更有效的方法可能是你的話的集存儲在一個線索結構，而不是一個列表。這是一個層次結構，每個節點都包含其子節點的前綴字符。這意味着您不必與所有單詞進行比較 - 一旦發現某個前綴匹配單詞而沒有前綴，則需要將其消除。

儘管對於50個單詞來說速度不太可能成爲問題，但trie可以使您儘量減少所需的字符比較次數，並且可以在遞歸層次結構時跟蹤字符數。

如果絕對的效率則要求在其中組織線索可能成爲例如，它可以組織有效率考慮反對而作出的搜索的實際統計的重要的精確的方式。

來源

2011-11-25 11:41:22 JARW

我將需要閱讀它以瞭解它是如何工作的。 –

謝謝你讓我知道更有效的方法。如果我能弄清楚如何編程，我可能會給你答案。 –

一個算法來判斷從列表中辨別出單詞需要多少個不同的主要字符？

回答

相關問題