Java two solutions - fast and slow DP


  • 0
    N

    Slow DP Solution

    I first came up with this solution. It is was significantly slower than the Fast method you will see later on. However, I feel it's easier to understand.

    keys:

    1. variable cur is the cursor for String T
    2. List<int[]> inds records all the index pair {start, end}, which satisfies S.substring(start, end) covered T.substring(0, cur+1);
    3. so that when cur continues to cur+1, the new List<int[]> inds would be built from the previous List<int[]> inds, by updating each end to the first index j after end and S.charAt(j) == T.charAt(the new cur)
    class Solution {
        public String minWindow(String S, String T) {
            
            List<int[]> inds = new ArrayList<>();
            
            for (int i=0; i<S.length(); i++) {
                if (S.charAt(i) == T.charAt(0)) {
                    inds.add(new int[]{i, i+1});
                }
            }
            
            int cur = 1;
            for (;cur < T.length() && inds.size() > 0; cur++) {
                
                List<int[]> newInds = new ArrayList<>();
                char target = T.charAt(cur);
                
                for (int[] ind : inds) {
                    int start = ind[1];
                    while (start < S.length()) {
                        if (S.charAt(start) == target) {
                            newInds.add(new int[]{ind[0], start+1});
                            break; // can break when founds a start, no need to continue and add everything into newInds
                        }
                        start++;   
                    }
                }
                inds = newInds;
            }
            
            if (cur < T.length() || inds.size() == 0) {
                return "";
            }
            
            int min = S.length()+1;
            int[] minSets = null;
            for (int[] ind : inds) {
                
                if (ind[1] - ind[0] < min) {
                    
                    minSets = ind;
                    min = ind[1] - ind[0];
                }
            }
            
            return S.substring(minSets[0], minSets[1]);
            
        }
        
    }
    

    Fast DP Solution

    (This solutions is essentially the same as the top 1 solution for C++)

    Keys:

    1. cur is the cursor for string T

    2. array inds records the start index of S's substring, which satisfies S.substring(inds[i], i+1) covers T[0, cur] for each 0<= i < S.length(). If at i there is no such a start index, set inds[i] = -1.

    3. over each iteration, use newInds to save the start indices for the current cur, newInds[i] = the largest j which satisfies S.charAt(i) == T.charAt(cur) and inds[j] != -1.

    4. use flag variable conContinue to determine if it's already impossible to cover the String T, so that the program can stop early.

    class Solution {
        public String minWindow(String S, String T) {
            
            int[] inds = new int[S.length()];
            boolean cont = false;
            
            for (int i=0; i<S.length(); i++) {
                if (S.charAt(i) == T.charAt(0)) {
                    
                    inds[i] = i;
                    cont = true;
                } else {
                    inds[i] = -1;
                }
            }
            
            if(!cont) {
                inds = null;
            }
            
            int cur = 1;
            for (;cur < T.length() && inds != null; cur++) { 
                
                int[] newInds = new int[S.length()];
                Arrays.fill(newInds, -1);
                
                boolean canContinue = false;
                
                char target = T.charAt(cur);
                
                for (int i=0; i<S.length(); i++) {
                    char c = S.charAt(i);
                    if (c == target) {
                        for (int j = i-1; j>=0; j--) {
                            if (inds[j] >= 0) {
                                newInds[i] = inds[j];
                                canContinue = true;
                                break;
                            }
                        }
                    }
                    
                }
                
                if (!canContinue) {
                    inds = null;
                    break;
                }
    
                inds = newInds;
            
            }
            
            
            if (inds == null) {
                return "";
            }
            
            int min = S.length()+1;
            int minInd = -1;
            for (int i = 0; i< inds.length; i++) {
                if (inds[i] < 0) {
                    continue;
                }
                
                if (i - inds[i] + 1 < min) {
                    
                    minInd = i;
                    min = i- inds[i] + 1;
                }
               
            }
            return S.substring(inds[minInd], minInd+1);    
        }
        
    }
    

Log in to reply
 

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