南昌公司做网站需要多少钱,网站维护工作方案,中山市 有限公司网站建设,资产管理系统源码给定一个单词列表#xff0c;我们将这个列表编码成一个索引字符串 S 与一个索引列表 A。
例如#xff0c;如果这个列表是 [time, me, bell]#xff0c;我们就可以将其表示为 S time#bell# 和 indexes [0, 2, 5]。
对于…给定一个单词列表我们将这个列表编码成一个索引字符串 S 与一个索引列表 A。
例如如果这个列表是 [time, me, bell]我们就可以将其表示为 S time#bell# 和 indexes [0, 2, 5]。
对于每一个索引我们可以通过从字符串 S 中索引的位置开始读取字符串直到 # 结束来恢复我们之前的单词列表。
那么成功对给定单词列表进行编码的最小字符串长度是多少呢
思路
这道题就是求字符串后缀如果字符串a的后缀包含字符串b那么b就不用再添加
字典树
先将字符串数组按照长度排序将字符串长的先添加进去之后遍历长度短的。
按照逆序将字符串插入字典树后面的字符串如果可以在字典树之中找到那么就不用添加这个字符串反之将这个字符串也逆序插入字典树
示例
输入: words [time, me, bell] 输出: 10 说明: S time#bell# indexes [0, 2, 5] 。
提示
1 words.length 2000 1 words[i].length 7 每个单词都是小写字母 。
代码
class Solution { public Tree root new Tree(); class Tree{ Tree children[] new Tree[26]; char val; } public int minimumLengthEncoding(String[] words) { if(words.length0){ return 0; } Arrays.sort(words, (s1, s2) - s2.length() - s1.length()); int count 0; for(int i0;iwords.length;i) { countinsert(words[i]); } return count; } public int insert(String word) { Tree cur root; boolean isNew false; for(int iword.length()-1;i0;i--) { int c word.charAt(i)-a; if(cur.children[c]null) { isNew true; cur.children[c] new Tree(); } cur cur.children[c]; } return isNew?word.length()1:0; }
}
