Longest String Chain

Nov 10, 2019

Given a list of words, each word consists of English lowercase letters.

Let’s say word1 is a predecessor of word2 if and only if we can add exactly one letter anywhere in word1 to make it equal to word2. For example, "abc" is a predecessor of "abac".

A word chain is a sequence of words [word_1, word_2, ..., word_k] with k >= 1, where word_1 is a predecessor of word_2, word_2 is a predecessor of word_3, and so on.

Return the longest possible length of a word chain with words chosen from the given list of words.

Example 1:

Input: ["a","b","ba","bca","bda","bdca"]
Output: 4
Explanation: one of the longest word chain is "a","ba","bda","bdca".


Note:

1. 1 <= words.length <= 1000
2. 1 <= words[i].length <= 16
3. words[i] only consists of English lowercase letters.

$$dp[i] = max({dp[j] + 1 | isPredecessor(words[i], words[j]) == true });$$

bool isPredecessor(string &s1, string &s2) {
// check s2 is s1's predecessor

if (s1.size() != s2.size() + 1) return false;

int i = 0;
int len = s2.size();
for(;i < len  && s1[i] == s2[i]; i++)
/* pass */;
for(;i < len && s1[i+1] == s2[i]; i++)
/* pass */;

return i == len;
}
int longestStrChain(vector<string>& words) {

// sort by size
sort(words.begin(), words.end(), [](const string &s1, const string &s2) {
return s1.size() < s2.size();
});

vector<int> dp(words.size(), 1);
int beg = 0;
int res = 0;

for(int i = 1;i < dp.size(); i++) {
while(words[beg].size() + 1 < words[i].size()) beg++;

for(int j = beg; j < i; j++) {
if (isPredecessor(words[i], words[j])) dp[i] = max(dp[i], dp[j] + 1);
}

res = max(dp[i], res);
}

return res;
}

LeetCodeLeetCode

Sort Characters By Frequency

Reverse Substrings Between Each Pair of Parentheses