6394. 字符串中的额外字符 (opens new window)

1.动态规划

解题思路：定义dp[j]表示以j索引下标结束的字符串，分割后最小剩余字符串长度。转移方程如下：

细节：

• 搜索时需要保证字符串中，所有起始位置的子串都要被搜索匹配到。头尾指针搜索复杂度为O(n^2)。
• 头指针为0时，需要对dp数组做初始化处理。
• 用list容器集合保存字典，调用contains()判断子串是否命中字典。

class Solution {
    public int minExtraChar(String s, String[] dictionary) {
        int strlen=s.length();
        int[] dp=new int[strlen];
        List<String> list=new ArrayList<>(Arrays.asList(dictionary));
        for(int i=0;i<strlen;i++){
            for(int j=i;j<strlen;j++){
                if(list.contains(s.substring(i,j+1))){
                    if(i==0){
                        dp[j]=0;
                    }
                    else{
                        dp[j]=dp[i-1]<dp[j]?dp[i-1]:dp[j];
                    }                 
                }
                else{
                    if(i==0){
                        dp[j]=j-i+1;
                    }
                    else{
                        dp[j]=dp[j-1]+1<dp[j]?dp[j-1]+1:dp[j];
                    }
                }
            }
        }
        return dp[strlen-1];
    }
}

2.dfs深搜

😭😭😭超时了没过，仅分享思路

dfs返回起始下标为index的字符串，分割后剩余的最小字符串长度。每个index起始的字符串搜索时都需要O(n^2)复杂度，保证所有子串都被搜索到。只要某个子串可以被字典匹配，则递归搜索子串后面的字符串。

超时原因在于没有剪枝，暂时没想到剪枝的方法。

class Solution {
    public int minExtraChar(String s, String[] dictionary) {
        List<String> list=new ArrayList<>(Arrays.asList(dictionary));
        return dfs(s,list,0);

    }
    public int dfs(String s,List<String> list,int index){
        if(index==s.length()) return 0;
        int min=s.length()-index;
        for(int i=index;i<s.length();i++){
            for(int j=i;j<s.length();j++){
                if(list.contains(s.substring(i,j+1))){
                    int temp=i-index+dfs(s,list,j+1);
                    min=temp<min?temp:min;
                }
            }
        }
        return min;
    }                              
}