每日一题：最长字符串链 - 刷题题解

给出一个单词数组 words ，其中每个单词都由小写英文字母组成。

如果我们可以不改变其他字符的顺序，在 wordA 的任何地方添加恰好一个字母使其变成 wordB ，那么我们认为 wordA 是 wordB 的前身。

词链是单词 [word_1, word_2, ..., word_k] 组成的序列， k >= 1 ，其中 word1 是 word2 的前身，word2 是 word3 的前身，依此类推。一个单词通常是 k = 1 的单词链。

从给定单词列表 words 中选择单词组成词链，返回词链的最长可能长度。

题目链接：https://leetcode.cn/problems/longest-string-chain/

# 方法一

PS：有点像最长上升子数组

	class Solution {
	public int longestStrChain(String[] words) {
	Arrays.sort(words, (s1, s2) -> s1.length() - s2.length());

	int n = words.length;
	int[] dp = new int[n];
	int max = 0;
	for(int i = 1; i < n; ++i) {
	for (int j = i - 1; j >= 0; --j) {
	if (check(words[j], words[i])) {
	dp[i] = Math.max(dp[i], dp[j] + 1);
	}
	}

	max = Math.max(max, dp[i]);
	}

	return max + 1;
	}

	private boolean check(String s, String t) {
	if (s == null \|\| t == null \|\| s.length() < 1 \|\| s.length() + 1 != t.length())
	return false;

	char[] schs = s.toCharArray();
	int lens = schs.length;
	int lost = 0;
	int j = 0;
	for (char c : t.toCharArray()) {
	if (j >= lens \|\| schs[j] != c) {
	++lost;
	} else {
	++j;
	}
	}

	return j == lens && lost == 1;
	}
	}

	class Solution {
	public int longestStrChain(String[] words) {
	Map<String, Integer> cntMap = new HashMap<>();
	Arrays.sort(words, (a, b) -> a.length() - b.length());
	int res = 0;
	for (String w : words) {
	int maxLen = 1;
	// 一次去调一个字符，再进行比对
	for (int i = w.length() - 1; i >= 0; --i) {
	String s = w.substring(0, i) + w.substring(i + 1);
	maxLen = Math.max(maxLen, cntMap.getOrDefault(s, 0) + 1);
	}
	// 加上本身
	res = Math.max(res, maxLen);
	cntMap.put(w, maxLen);
	}
	return res;
	}
	}