単語の圧縮符号化(中等)辞書ツリー/接頭辞ツリー/Tree数
タイトル:単語リストを与え、このリストをインデックス文字列SとインデックスリストAに符号化する.たとえば、このリストが["time","me","bell"]の場合、S="time#bell#",indexes=[0,2,5]と表すことができます.各インデックスについては、文字列S内のインデックスの位置から文字列の読み取りを開始し、「#」が終了するまで、前の単語リストを復元できます.では、与えられた単語リストを符号化することに成功した最小文字列の長さはどのくらいですか.
例:入力:words=["time","me","bell"]出力:10説明:S="time#bell#",indexes=[0,2,5].
出典:力ボタン(LeetCode)
最初は文字列の配列全体を遍歴することを考えていましたが、後者が前の接尾辞であれば長さは変わりません.そうしないと、総長+1に後の単語の長さが加算されます.しかし、例を見ると、このような考えは何の問題もありませんが、肝心なのは、長さが前で、長さが後であれば、間違いが発生することです.
だから調べた後、辞書ツリーというデータ構造を学びました.
すなわち、1つのノード内に長さ26のノード配列が含まれている.各ノードの配列内の位置はa,b,cを表す.
本題では、接尾辞を考えているので、各単語を末尾から辞書ツリーに追加します.このように総長さは、すべての葉のノードからルートノードまでの長さの和である.注意:単語が辞書ツリーに追加される順序は、長さから短さです.
コード:
例:入力:words=["time","me","bell"]出力:10説明:S="time#bell#",indexes=[0,2,5].
出典:力ボタン(LeetCode)
最初は文字列の配列全体を遍歴することを考えていましたが、後者が前の接尾辞であれば長さは変わりません.そうしないと、総長+1に後の単語の長さが加算されます.しかし、例を見ると、このような考えは何の問題もありませんが、肝心なのは、長さが前で、長さが後であれば、間違いが発生することです.
だから調べた後、辞書ツリーというデータ構造を学びました.
すなわち、1つのノード内に長さ26のノード配列が含まれている.各ノードの配列内の位置はa,b,cを表す.
本題では、接尾辞を考えているので、各単語を末尾から辞書ツリーに追加します.このように総長さは、すべての葉のノードからルートノードまでの長さの和である.注意:単語が辞書ツリーに追加される順序は、長さから短さです.
コード:
class Solution {
public int minimumLengthEncoding(String[] words) {
if(words.length == 0)
return 0;
if(words[0].length() == 1)
return words[0].length()+1;
StringBuffer sb = new StringBuffer();
Arrays.sort(words,new Comparator<String>(){
public int compare(String s1,String s2){
if(s1.length() == s2.length())
return 0;
return s1.length()>s2.length()?-1:1;
}
});
int res = 0;
TreeNode root = new TreeNode(0);
for(String s:words)
res += root.insert(s);
return res;
}
}
class TreeNode{
public int val;
public TreeNode[]child;
public TreeNode(int x){
child = new TreeNode[26];
val = x;
}
public int insert(String word){
boolean isNew = false;
TreeNode t = this;
for(int i = word.length()-1;i>=0;i--){
if(t.child[word.charAt(i)-'a'] == null){
isNew = true;
t.child[word.charAt(i)-'a'] = new TreeNode(word.charAt(i)-'a');
}
t = t.child[word.charAt(i)-'a'];
}
return isNew?word.length()+1:0;
}
}