Java Easy O(S*T) time(40ms) Solution


  • 0
    K

    Java Optimal Solution(40 ms)

    class Solution {
        public String minWindow(String S, String T) {
            int min=-1,idx=-1,slen=S.length(),tlen=T.length();
            char[] Tc=T.toCharArray();
            char[] Sc= S.toCharArray();
            int[][] dp= new int[slen][26];
            
            for(int i=slen-2;i>=0;i--){
                for(int j=0;j<26;j++){
                    if(Sc[i+1]== j+'a') dp[i][j]=i+1;
                    else dp[i][j]=dp[i+1][j];
                }
            }
            
            for(int i=0;i<slen;i++){
               if(Sc[i]!=Tc[0]) continue;
                int len= helper(dp,Tc,i);
                if(len==-1) break;
                if(min==-1 || len<min){
                    idx=i;
                    min=len;
                }
            }
            if(min==-1) return "";
            return S.substring(idx,idx+min);
        }
        
        public int helper(int[][] dp,char[] Tc, int pos){
            int i=1;
            int start=pos;
            for(;i<Tc.length;i++){
                if(dp[pos][Tc[i]-'a']==0) break;
                else pos= dp[pos][Tc[i]-'a'];
            }
            if(i==Tc.length) return pos-start+1;
            else return -1;
        }
    }
    

    Java BruteForce Solution

    class Solution {
        public String minWindow(String S, String T) {
            int min=-1,idx=-1;
            char[] Tc=T.toCharArray();
            char[] Sc=S.toCharArray();
            for(int i=0;i<S.length();i++){
                int len=check(Tc,Sc,i);
                if(len<=0) break;
                if(min==-1 || len<min){
                    idx=i;
                    min=len;
                }
            }
            if(min==-1) return "";
            return S.substring(idx,idx+min);
        }
        
        public int check(char[] Tc,char[] Sc, int start){
            int i=start,j=0;
            while(i<Sc.length && j<Tc.length){
                if(Sc[i]==Tc[j]) j++;
                i++;
            }
            if(j==Tc.length) return i-start;
                  return -1;
        }
    }
    

  • 0
    D

    Typical dp solution is O(SxTxlog(S)), this brutal force is O(S^2). It will perform badly when S >> T.


  • 0
    K

    @derek3 I have added a O(S*T) solution.


Log in to reply
 

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