1055. Shortest Way to Form String

greedy O(m+n) time
f[i][c]表示在source中从下标i开始第一次出现的字母c在source中的下标，这样做可以跳过中间不符合要求的那些字母方便快速查找

class Solution {
public:
    int shortestWay(string source, string target) {
        int m = source.length(), n = target.length();
        vector<vector<int>> f(m, vector<int>(26, -1));
        f[m - 1][source[m - 1] - 'a'] = m - 1;
        for (int i = m - 2; i >= 0; --i) {
            f[i] = f[i + 1]; // 先copy后一个index的内容
            f[i][source[i] - 'a'] = i; // 再修改当前index所对应的字符的下标
        }
        int res = 1, i = 0; // res要从1开始因为target最后一个字符结束以后没法更新res
        for (char c : target) {
            if (f[0][c - 'a'] == -1) return -1; // 如果source所有字符里都不包含c
            if (i == m || f[i][c - 'a'] == -1) { // 如果source所有字符都比对完或者尚未比对完但是source当前位置之后没有c（之前可能有）则重置指针并更新res
                i = 0;
                ++res;
            }
            i = f[i][c - 'a'] + 1; // 移动指针到下一个可能的位置（跳过中间不符合要求的字符）
        }
        return res;
    }
};

greedy O(m*n) time
worst case比如[“abcd”, “ddddd”]

class Solution {
public:
    int shortestWay(string source, string target) {
        int m = size(source), n = size(target);
        int res = 0;
        for (int i = 0; i < n;) {
            int t = i;
            for (int j = 0; j < m; ++j) {
                if (i < n && source[j] == target[i]) {
                    ++i;
                }
            }
            if (i == t) return -1;
            ++res;
        }
        return res;
    }
};

class Solution {
public:
    int shortestWay(string source, string target) {
        int m = source.length(), n = target.length();
        bool f[26] = {false};
        for (char c : source) {
            f[c - 'a'] = true;
        }
        int res = 1;
        for (int i = 0, j = 0; i < n; ++i, ++j) {
            if (!f[target[i] - 'a']) return -1;
            while (j < m && source[j] != target[i]) ++j;
            if (j == m) {
                j = -1;
                --i;
                ++res;
            }
        }
        return res;
    }
};

dp O(m*m+(n-m)*n) time
f[i]表示target前i个字符需要几个source的子序列才能构成

class Solution {
public:
    int shortestWay(string source, string target) {
        int m = source.length(), n = target.length();
        vector<int> f(n + 1, INT_MAX);
        f[0] = 0;
        for (int i = 1; i <= n; ++i) {
            int k = m - 1;
            for (int j = i - 1; j >= 0; --j) {
                while (k >= 0 && source[k] != target[j]) --k;
                if (k == -1) {
                    if (f[i] == INT_MAX) return -1;
                    break;
                } else {
                    f[i] = min(f[i], f[j] + 1);//cout<<"f["<<i<<"] = "<<f[i]<<endl;
                    --k;
                }
            }
        }
        return f[n];
    }
};