力扣 2707.字符串中的额外字符（动态规划）

力扣 2707.字符串中的额外字符

动态规划

f[0] = 0;
s字符串长度为n，求f[n]
f[n] = ((f[n - 1] + 1) < f[j : n]) ? (f[n - 1] + 1) : f[j : n];  (其中 j <= n)
其中f[j : n]为字符串第j位到第n位，这里需要满足f[j : n]为字典中所出现的字符串
因此，可以通过起始f[0]以及动态规划的思想，可以推导出f[n],即为字符串中最少得额外字符
注：在求f[n]的时候，需要判断所有的f[j : n]是否在字典中出现，及每一个字典中的字符串都需要判断一下，从而求得最小值f[n]

代码.cpp

class Solution {
public:
    int minExtraChar(string s, vector<string>& dictionary) {
        int f[52] = {0};
        for (int i = 0; i < 52; i++) {
            f[i] = 100;
        }
        f[0] = 0;
        for (int i = 1; i <= s.length(); i++) {
            string str = s.substr(0, i);
            for (int j = 0; j < dictionary.size(); j++) {
                if (dictionary[j].length() <= str.length()) {
                    string strData =
                        str.substr(str.length() - dictionary[j].length(),
                                   dictionary[j].length());
                    if (strData == dictionary[j]) {
                        if (f[i] > f[i - strData.length()]) {
                            f[i] = f[i - strData.length()];
                        }
                    }
                }
            }
            if (f[i] > f[i - 1] + 1) {
                f[i] = f[i - 1] + 1;
            }
            if (f[i] == 100) {
                f[i] = f[i - 1] + 1;
            }
        }
        return f[s.length()];
    }
};