最长字符串链【LC1048】
给出一个单词数组
words，其中每个单词都由小写英文字母组成。如果我们可以 不改变其他字符的顺序 ，在
wordA的任何地方添加 恰好一个 字母使其变成
wordB ，那么我们认为 wordA 是 wordB 的 前身 。
- 例如，
"abc"是"abac"的 前身 ，而"cba"不是"bcad"的 前身 - 词链是单词
[word_1, word_2, ..., word_k]组成的序列，k >= 1，其中word1是word2的前身，word2是word3的前身，依此类推。一个单词通常是k == 1的 单词链 。
从给定单词列表 words 中选择单词组成词链，返回 词链的 最长可能长度 。
到家啦 happy
- 思路
某个单词的前身单词的长度一定比该单词少1，因此可以将单词根据长度升序排列。然后通过动态规划找到词链的最长长度，定义dp[i]为以words[i]为词链末尾的最长词链长度，如果words[j]是words[i]的前身，那么判断是否需要更新dp[i]。 - 实现
class Solution { public int longestStrChain(String[] words) { Arrays.sort(words, (o1, o2) -> o1.length() - o2.length()); int n = words.length; int[] dp = new int[n]; Arrays.fill(dp, 1); int res = 0; for (int i = 0; i < n; i++){ for (int j = 0; j < i; j++){ if (isPredecessor(words[i], words[j])){ dp[i] = Math.max(dp[i], dp[j] + 1); } } res = Math.max(res, dp[i]); } return res; } // 判断s2是否是s1的前身 public boolean isPredecessor(String s1, String s2){ int n = s1.length(), m = s2.length(); if (n != m + 1) return false; int i = 0, j = 0; while (i < n && j < m){ if (s1.charAt(i) == s2.charAt(j)){ j++; } i++; } return j == m; } }
