You've successfully subscribed to The Daily Awesome
Great! Next, complete checkout for full access to The Daily Awesome
Welcome back! You've successfully signed in.
Success! Your account is fully activated, you now have access to all content.
Success! Your billing info is updated.
Billing info update failed.

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

. 3 min read

【动态规划】

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

如果我们可以在 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)

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) 官方目前最快答案

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;
	}
	
}