# 最长字符串链 - 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)

 `````` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 `````` ``````class Solution { public int longestStrChain(String[] words) { int len = words.length; /* 将字符串按照字典序重新排列 */ Arrays.sort(words, new Comparator() { @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) 官方目前最快答案

 `````` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 `````` ``````class Solution { public ArrayList> 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 subList = new ArrayList(); list.add(subList); } for(String string : words) { list.get(string.length()-1).add(string); } for(int i = 0;i < dp.length;i++) { ArrayList 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 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; } } ``````