因此对于每个字符串 s,假设其所有的前身 s’ 为结尾的最长链的长度为 l,即可知道以 s 为结尾的最长链的长度为 l + 1。为保证我们求 s 的最长链时,其所有的前身的最长链的长度均已求出,需要将所有的字符串按照长度大小进行排序。假设字符串 s 最长链的长度为 cnt}(s) 的前身为 s’{0},s’{1},s’{2}, \cdots,s’{k,则此时可以知道
\textit{cnt}(s) = \max(\textit{cnt}(s’_{i})), \quad i \in [0,k]
classSolution { public: intlongestStrChain(vector<string>& words){ unordered_map<string, int> cnt; sort(words.begin(), words.end(), [](const string &a, const string &b) { return a.size() < b.size(); }); int res = 0; for (string word : words) { cnt[word] = 1; for (int i = 0; i < word.size(); i++) { string prev = word.substr(0, i) + word.substr(i + 1); if (cnt.count(prev)) { cnt[word] = max(cnt[word], cnt[prev] + 1); } } res = max(res, cnt[word]); } return res; } };
[sol1-Java]
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
classSolution { publicintlongestStrChain(String[] words) { Map<String, Integer> cnt = newHashMap<String, Integer>(); Arrays.sort(words, (a, b) -> a.length() - b.length()); intres=0; for (String word : words) { cnt.put(word, 1); for (inti=0; i < word.length(); i++) { Stringprev= word.substring(0, i) + word.substring(i + 1); if (cnt.containsKey(prev)) { cnt.put(word, Math.max(cnt.get(word), cnt.get(prev) + 1)); } } res = Math.max(res, cnt.get(word)); } return res; } }
[sol1-Python3]
1 2 3 4 5 6 7 8 9 10 11 12 13
classSolution: deflongestStrChain(self, words: List[str]) -> int: cnt = defaultdict(int) words.sort(key=len) res = 0 for word in words: cnt[word] = 1 for i inrange(len(word)): prev = word[:i] + word[i+1:] if prev in cnt: cnt[word] = max(cnt[word], cnt[prev] + 1) res = max(res, cnt[word]) return res
intlongestStrChain(char ** words, int wordsSize) { HashItem *cnt = NULL; qsort(words, wordsSize, sizeof(char *), cmp); int res = 0; for (int i = 0; i < wordsSize; i++) { hashAddItem(&cnt, words[i], 1); char prev[32]; for (int j = 0; words[i][j] != '\0'; j++) { strcpy(prev + j, words[i] + j + 1); if (hashFindItem(&cnt, prev)) { int len = hashGetItem(&cnt, prev, 0) + 1; int cur = hashGetItem(&cnt, words[i], 0); if (len > cur) { hashSetItem(&cnt, words[i], len); } } prev[j] = words[i][j]; } int cur = hashGetItem(&cnt, words[i], 0); if (cur > res) { res = cur; } } hashFree(&cnt); return res; }
[sol1-Go]
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
funclongestStrChain(words []string)int { cnt := map[string]int{} sort.Slice(words, func(i, j int)bool { returnlen(words[i]) < len(words[j]) }) res := 0 for _, word := range words { cnt[word] = 1 for i := range word { prev := word[:i] + word[i + 1:] if j := cnt[prev] + 1; j > cnt[word] { cnt[word] = j } } if cnt[word] > res { res = cnt[word] } } return res }
[sol1-JavaScript]
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
var longestStrChain = function(words) { const cnt = newMap(); words.sort((a, b) => a.length - b.length); let res = 0; for (const word of words) { cnt.set(word, 1); for (let i = 0; i < word.length; i++) { const prev = word.substring(0, i) + word.substring(i + 1); if (cnt.has(prev)) { cnt.set(word, Math.max(cnt.get(word), cnt.get(prev) + 1)); } } res = Math.max(res, cnt.get(word)); } return res; };
复杂度分析
时间复杂度:O(n \times m \times (\log n + m)),其中 n 表示字符串数组的长度,m 表示每个字符串的平均长度。首选对字符串数组进行排序,需要的时间为 O(n \times m \times \log n),然后遍历每个字符串,并对每个字符串都生成其「前身」字符串,需要的时间为 O(n \times m^2),因此总的时间复杂度为 O(n \times m \times (\log n + m))。
空间复杂度:O(n\times m),其中 n 表示字符串数组的长度,m 表示每个字符串的平均长度。需要存储以每个字符串为结尾的最大链的长度,一共有 n 个字符串,每个字符串的平均长度为 m,因此需要的空间为 O(n\times m)。