毎日1題--単語の圧縮符号化

Trieは単語検索ツリーとも呼ばれ、Trieツリーはツリー構造であり、ハッシュツリーの変種である.本人ノートは、与えられた単語リストを無視することができ、このリストをインデックス文字列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].
ヒント:
1 <= words.length <= 2000 1 <= words[i].length<=7各単語は小文字です.
ソース:力ボタン(LeetCode)リンク:https://leetcode-cn.com/problems/short-encoding-of-words著作権はインターネットの所有に帰属する.商業転載は公式の授権に連絡してください.非商業転載は出典を明記してください.
この问题はどういう意味ですか??兄弟も私と同じかもしれませんが、最初は読めませんでした.ちょっと説明しますが、わかる兄弟は無視すればいいです.
テーマは2つのインデックスを与えた.1つはS=「time#bell#」,indexes=[0,2,5].まずindexesの最初の0がSの0から#の終わりであるtimeの2番目が2から始まりmeの3番目が5番目の始まりであるbellを見てみましょう
私の考えを言って、私がまず考えたのは私たちが2つの単語の含むことと含まれる関係の方法を見つけることです1:私たちは接尾辞が含まれていない単語だけを保存することができます

public class ShortEncodingOfWords {
     
	public int minimumLengthEncoding(String[] words) {
     
	    Set<String> good = new HashSet(Arrays.asList(words));// HashSet 
	    for (String word:words) {
     // 
	    	 for (int k = 1;k < word.length() ; ++ k){
     
	    		 good.remove(word.substring(k));// hashset 
	    	 }
	    }
	    int ans = 0;
	    for(String word : good) 
	    	ans += word.length() + 1;
		return ans;
    }
}

方法2:辞書ツリーは、方法1で述べたように、他の単語の接尾辞ではないすべての単語を保持することを目標としています.

class Solution {
     
    public int minimumLengthEncoding(String[] words) {
     
        TrieNode trie = new TrieNode();
        Map<TrieNode, Integer> nodes = new HashMap();

        for (int i = 0; i < words.length; ++i) {
     
            String word = words[i];
            TrieNode cur = trie;
            for (int j = word.length() - 1; j >= 0; --j)
                cur = cur.get(word.charAt(j));
            nodes.put(cur, i);
        }

        int ans = 0;
        for (TrieNode node: nodes.keySet()) {
     
            if (node.count == 0)
                ans += words[nodes.get(node)].length() + 1;
        }
        return ans;

    }
}

class TrieNode {
     
    TrieNode[] children;
    int count;
    TrieNode() {
     
        children = new TrieNode[26];
        count = 0;
    }
    public TrieNode get(char c) {
     
        if (children[c - 'a'] == null) {
     
            children[c - 'a'] = new TrieNode();
            count++;
        }
        return children[c - 'a'];
    }
}

作者:LeetCode-Solutionリンク:https://leetcode-cn.com/problems/short-encoding-of-words/solution/dan-ci-de-ya-suo-bian-ma-by-leetcode-solution/出典:力扣(LeetCode)著作権は作者の所有である.商業転載は著者に連絡して許可を得てください.非商業転載は出典を明記してください.