day-04 字符串中的额外字符

思路
动态规划，每个字符要么额外要么不是额外

解题方法
int[] dp = new int[n+1];
dp[i] 表示从字符串开头到字符串索引i位置的最少额外字符数
dp[i + 1] = Math.min(dp[i + 1], dp[j])
dp[j]表示假设s第i个字符不是额外的，可能等于dp[i + 1]，也可能等于dp[i + 1]-1

code

class Solution {

    public int minExtraChar(String s, String[] dictionary) {

        int n = s.length();
        int[] dp = new int[n+1];  // dp[i+1] 表示从字符串开头到字符串索引i位置的最少额外字符数
        Set<String> dictionarySet = new HashSet<>();
        for(String word: dictionary){

            dictionarySet.add(word);        //依次存入set中
        }
        for(int i = 0; i < n; i++){

            dp[i + 1] = dp[i] + 1;  // 字符串i对应的位置字符是额外字符
            for(int j = 0; j <= i; j++){
       // 假设字符串i对应的位置字符是额外字符
                if(dictionarySet.contains(s.substring(j, i + 1))){

                    dp[i + 1] = Math.min(dp[i + 1], dp[j]);
                }
            }
        }
        return dp[n];   // dp[n] 即为额外最少字符数
    }
}

substring(int beginIndex)：从指定索引位置 beginIndex（包括）开始截取字符串的剩余部分。

substring(int beginIndex, int endIndex)：从指定索引位置 beginIndex（包括）开始截取字符串，直到索引位置 endIndex（不包括）为止。

dictionarySet.contains(s.substring(j, i + 1)) set中是否有字符串 s[i]–s[j-1]

注：不会，看了题解，哈哈。。。。。。

原文链接: https://blog.csdn.net/qq_53568730/article/details/135490237