727. Minimum Window Subsequence

Description

457-1

Solution

There are two solutions, one is original DP(very common solution that must think of it when encounter a string problem), another is Finite State Machine solution.

DP

1
2
3
4
5
6
7
8
9
DP[i][j] = the minimum subsequence length k
//e.g, s2[0 : j] is a subsequence of s1[i - k + 1: i]

if s1[i] == s2[j]
	dp[i][j] = dp[i-1][j-1] + 1
else
	dp[i][j] = dp[i-1][j] + 1

return min{dp[i][N]} for i= 1,2,3..M

Finite State Machine

1
2
3
4
5
6
7
Define a array next[i][ch]: look right from position i, the pos of the nearest ch

With the next[][], we directly jump into next nearest matched postion without iterate.

And the way to calculate next is DP, we see from back to front

next[i][ch] = next[i+1][ch](except next[i][s[i+1] - 'a'] = i+1)

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
class Solution {
public:
    string minWindow(string s1, string s2) {
        if(s1.size() < s2.size())
            return "";
        //DP
        // vector<vector<int>> dp(s1.size() + 1, vector<int>(s2.size() + 1, INT_MAX));
        // for(int i = 0; i <= s1.size(); i++)
        //     dp[i][0] = 0;
        // for(int i = 1; i <= s1.size(); i++){
        //     for(int j = 1; j <= s2.size() && j <= i; j++){
        //         if(s1[i-1] == s2[j-1] && dp[i-1][j-1] != INT_MAX)
        //             dp[i][j] = dp[i-1][j-1] + 1;
        //         else if(s1[i-1] != s2[j-1] && dp[i-1][j] != INT_MAX)
        //             dp[i][j] = dp[i-1][j] + 1;
        //     }
        // }
        // string res = "";
        // for(int i = 1; i <= s1.size(); i++){
        //     if((res == "" && dp[i][s2.size()] != INT_MAX) || res.size() > dp[i][s2.size()]){
        //         res = s1.substr(i-dp[i][s2.size()], dp[i][s2.size()]);
        //     }
        // }

        //Finite-State-Machine
        vector<vector<int>> next(s1.size(), vector<int>(26,0));
        for(int i = 0; i < 26; i++){
            next[s1.size()-1][i] = -1;
        }
        for(int i = s1.size()-2; i >= 0; i--){
            for(int j = 0; j < 26; j++)
                next[i][j] = next[i+1][j];
            next[i][s1[i+1] - 'a'] = i+1;
        }
        string res = "";
        int length = INT_MAX, start;
        for(int i = 0; i < s1.size(); i++){
            if(s1[i] == s2[0]){
                int j = i, s2i = 1;
                while(s2i < s2.size() && next[j][s2[s2i] - 'a'] != -1){
                    j = next[j][s2[s2i++] - 'a'];
                }
                if(s2i == s2.size()){
                    if(length > j - i + 1){
                        start = i;
                        length = j - i + 1;
                    }
                }
            }
        }

        if(length != INT_MAX)
            res = s1.substr(start, length);
        return res;
    }
};

457-2