DP method: memory limits exceed!!!


  • 0
    T
    
    public class Solution {
        public boolean isSubsequence(String s, String t) {
            if(s==null||t==null) return s==t;
            if(s.length()>=t.length()) return s.equals(t);
            if(s.length()==0) return true;
            
            char[] s_array = s.toCharArray();
            char[] t_array = t.toCharArray();
            
            boolean[][] dp = new boolean[s_array.length+1][t_array.length+1];
            for(int j=0;j<=t_array.length;j++){
                dp[0][j]=true;
            }
            
            for(int i=0;i<s_array.length;i++){
                for(int j=i;j<t_array.length;j++){
                    if(s_array[i]==t_array[j]){
                        dp[i+1][j+1]=dp[i][j];
                    }else{
                        dp[i+1][j+1]=dp[i+1][j];
                    }
                }
            }
            
            return dp[s_array.length][t_array.length];
        }
    }
    
    

Log in to reply
 

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