这题分两个步骤:
-
判断每个单词对能否相互之间有关系(predecessor)。如果有关系,新建一条从word1到word2的有向边
-
计算有向无环图的最长路径
因为按单词长度排序就是这个图的拓扑排序, 那么我们可以直接按词长排序后,边判断单词是否有predecessor,边用dp记录当前最长长度。
时间复杂度O(nlogn + n*m)
typedef pair<int, int> PII;
class Solution {
public:
int longestStrChain(vector<string>& words) {
int n = words.size(), ans = 0;
vector<PII> arr(n);
for (int i = 0; i<n; i++)
arr[i] = {words[i].size(), i};
sort(arr.begin(), arr.end());
unordered_map<string, int> dict;
vector<int> dp(n+1, 1);
for (int i = 0; i<n; i++){
string &str = words[arr[i].second];
int m = str.size();
for (int j = 0; j<m; j++){
string tmp = str.substr(0, j) + str.substr(j+1);
if (dict.count(tmp))
dp[i] = max(dp[i], dp[dict[tmp]] + 1);
}
dict[str] = i;
ans = max(ans, dp[i]);
}
return ans;
}
};