You've successfully subscribed to The Daily Awesome
Welcome back! You've successfully signed in.
Success! Your billing info is updated.
Billing info update failed.

# 1048. 最长字符串链 - Longest String Chain

【动态规划】

## Example:

输入：["a","b","ba","bca","bda","bdca"]



1. 1 <= words.length <= 1000
2. 1 <= words[i].length <= 16
3. words[i] 仅由小写英文字母组成。

## Solution 【动态规划】 ( 119ms)

class Solution {
public int longestStrChain(String[] words) {
int len = words.length;
/* 将字符串按照字典序重新排列 */
Arrays.sort(words, new Comparator<String>() {
@Override
public int compare(String o1, String o2) {
return Integer.compare(o1.length(), o2.length());
}
});
/* dp[i] 表示 到 words[i] 为止最长的词链长度 */
int[] dp = new int[len];
for(int i = 0; i < len - 1; i++) {
String a = words[i];
for (int j = i + 1; j < len; j++) {
String b = words[j];
/* 判断 words[i] 是否是 words[j] 的前身 */
if (isPredecessor(a, b)) {
dp[j] = Math.max(dp[j], dp[i]+1);
}

}

}
/* 得到最终结果，由于最末尾的字符串不一定在最终词链里，因此dp[len-1]不一定是最终结果 */
int res = 0;
for (int i = 0; i < len; i++) {
if (res < dp[i])  res = dp[i];
}
return res + 1;
}

private boolean isPredecessor(String stra, String strb) {
int i = 0;  // 字符串A的指针
int j = 0;  // 字符串B的指针
int lenA = stra.length();
int lenB = strb.length();
/* 排除长度相差不为一的情况 */
if (lenA != lenB-1) {
return false;
}
char[] a = stra.toCharArray();
char[] b = strb.toCharArray();
while (i < lenA && j < lenB) {
if (a[i] == b[j]) {
i++;
}
j++;
}
return i == lenA;
}
}


## Solution 【动态规划】(40ms) 官方目前最快答案

class Solution {
public ArrayList<ArrayList<String>> list = new ArrayList<>();
public int maxLen = 1;
public int[][] dp = new int[17][1000];
public int longestStrChain(String[] words) {
for(int i = 0;i < dp.length;i++) {
ArrayList<String> subList = new ArrayList<String>();
}
for(String string : words) {
}
for(int i = 0;i < dp.length;i++) {
ArrayList<String> tempList = list.get(i);
for(int j = 0;j < tempList.size();j++) {
longestStrChain(tempList.get(j),i+1,1,j);
}
}
return maxLen;
}
public int longestStrChain(String preString,int index,int len,int subIndex) {
if(index == 17 || list.get(index).size() == 0) {
if(maxLen < len)
maxLen = len;
return len;
}else {
//System.out.println("index-1"+(index-1)+"::subIndex"+subIndex);
if(dp[index-1][subIndex] != 0)
return dp[index-1][subIndex];
ArrayList<String> tempList = list.get(index);
int max = len;
for(int i = 0;i < tempList.size();i++) {
String string = tempList.get(i);
if(checkPreStr(preString.toCharArray(), string.toCharArray())) {
dp[index][i] = longestStrChain(string,index+1,len+1,i);
if(dp[index][i] > max)
max = dp[index][i];
}
}
dp[index-1][subIndex] = max;
if(maxLen < max)
maxLen = max;
return max;
}

}

public boolean checkPreStr(char[] preStr,char[] str) {
int i = 0,j = 0,flag = 0;
for(;i < preStr.length && j < str.length;i++,j++) {
if(preStr[i] != str[j] && flag == 0) {
i--;
flag = 1;
}else if(preStr[i] != str[j] && flag == 1) {
return false;
}
}
return true;
}

}