820. Short Encoding of Words
Problem:
核心思想是合并suffix一样的单词。比如time和me,suffix是一个的,可以把me去掉。可以用2种方法做。
Approach 1: Hash set
先把所有的word加入到一个set里面。然后遍历所有word。 对于每一个word,从index 1开始拆分suffix, 看这个word的suffix在不在set里面。如果在则从set里面删除。
It's intuitive to come up with trie solution for this problem. Instead of constructing trie form prefix, we can use suffix. So the anwser will be the sum of the depth of the leaf nodes.
Given a list of words, we may encode it by writing a reference string
S
and a list of indexes A
.
For example, if the list of words is
["time", "me", "bell"]
, we can write it as S = "time#bell#"
and indexes = [0, 2, 5]
.
Then for each index, we will recover the word by reading from the reference string from that index until we reach a "#" character.
What is the length of the shortest reference string S possible that encodes the given words?
Example:
Input: words =Analysis:["time", "me", "bell"]
Output: 10 Explanation: S ="time#bell#" and indexes = [0, 2, 5
].
核心思想是合并suffix一样的单词。比如time和me,suffix是一个的,可以把me去掉。可以用2种方法做。
Approach 1: Hash set
先把所有的word加入到一个set里面。然后遍历所有word。 对于每一个word,从index 1开始拆分suffix, 看这个word的suffix在不在set里面。如果在则从set里面删除。
class Solution { public int minimumLengthEncoding(String[] words) { Set<String> set = new HashSet<>(Arrays.asList(words)); for (String word: words) { for (int i = 1; i < word.length(); i++) { set.remove(word.substring(i, word.length())); } } int res = 0; for (String s: set) { res += s.length() + 1; } return res; } }Approach 2:
It's intuitive to come up with trie solution for this problem. Instead of constructing trie form prefix, we can use suffix. So the anwser will be the sum of the depth of the leaf nodes.
class Solution { class TrieNode { public Map<Character, TrieNode> children = new HashMap<>(); public int depth; } public int minimumLengthEncoding(String[] words) { List<TrieNode> leaves = new ArrayList<>(); TrieNode root = new TrieNode(); int res = 0; for (String word: new HashSet<>(Arrays.asList(words))) { TrieNode cur = root; for (int i = word.length() - 1; i >= 0; i--) { char c = word.charAt(i); if (!cur.children.containsKey(c)) { cur.children.put(c, new TrieNode()); } cur = cur.children.get(c); } // the cur at this point is leaf node. cur.depth = word.length() + 1; leaves.add(cur); } for (TrieNode node: leaves) { if (node.children.isEmpty()) res += node.depth; } return res; } }
评论
发表评论