Java DP O(SxT)


  • 0
    J

    DP O(SxT)

    class Solution {
    public String minWindow(String S, String T) {  // O(S x T)
        char[] s = S.toCharArray();
        char[] t = T.toCharArray();
        int m = s.length, n = t.length;
        
        int[][] f = new int[m + 1][n + 1];
        int[][] ff = new int[m + 1][n + 1];
        
        for (int i = 0; i <= m; i++) {
            for (int j = 0; j <= n; j++) {
                f[i][j] = -1;
                ff[i][j] = j == 0 ? 0 : -1;
            }
        }
        
        f[0][0] = 0; // match
        // find all of the results
        for (int j = 1; j <= n; j++) {
            for (int i = 1; i <= m; i++) {
                if (s[i - 1] == t[j - 1]) {
                    if (ff[i - 1][j - 1] >= 0) {
                         f[i][j] = ff[i - 1][j - 1];
                         ff[i][j] = i;
                    }
                } else {
                    ff[i][j] = ff[i - 1][j];
                }
            }
        }
        
        // find the best result
        int start = -1, end = -1, min = Integer.MAX_VALUE;
        for (int i = 0; i <= m; i++) {
            if (f[i][n] >= 0) { // valid
                int index = i, count = n;
                while (count > 1) {
                    index = f[index][count--];
                }
                int l_start = index;
                if (i - l_start < min) {
                    min = i - l_start;
                    start = l_start;
                    end = i;
                } else if (i - l_start == min) {
                    if (l_start < start) {
                        start = l_start;
                        end = i;
                    }
                }
            }
        }
        return start == -1 ? "" : S.substring(start - 1, end);
    }
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.