1. 最长字符串链 - Longest String Chain

【动态规划】

Problem Link

给出一个单词列表,其中每个单词都由小写英文字母组成。

如果我们可以在 word1 的任何地方添加一个字母使其变成 word2,那么我们认为 word1word2 的前身。例如,"abc""abac" 的前身。

词链是单词 [word_1, word_2, ..., word_k] 组成的序列,k >= 1,其中 word_1word_2 的前身,word_2word_3 的前身,依此类推。

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

Example:

示例:

输入:["a","b","ba","bca","bda","bdca"]
输出:4
解释:最长单词链之一为 "a","ba","bda","bdca"。

提示:

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

Analysis

定义$dp[i]$ 表示 到 $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<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;
    }
}

复杂度分析

时间:$O(N^2)$

空间:$O(N)$

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<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>();
        	list.add(subList);
        }
		for(String string : words) {
			list.get(string.length()-1).add(string);
		}   
		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;
	}
	
}