Why i get TLE , I use backtracking and I have store the result of each step?


  • 0
    L

    public class Solution {

    boolean[][] isTrue ;
    
    boolean[][] visited ;
    public boolean match(String s, String p) {
        if( visited[s.length()][p.length()] ) return isTrue[s.length()][p.length()];
        visited[s.length()][p.length()] = true;
    
        if( s.length() == 0 || p.length() == 0 ) {
            if( s.length() > 0 ) {
                isTrue[s.length()][p.length()] = false;
                return false;
            }
            else {
                boolean flag = true;
                for( int i = 0 ; i < p.length() ; i ++ ) if( p.charAt(i) != '*' ) {
                    isTrue[s.length()][p.length()] = false;
                    flag = false;
                    break;
                }
                isTrue[s.length()][p.length()] = flag;
                return flag;
            }
        }
    
        if( s.charAt(0) == p.charAt(0) || p.charAt(0) == '?' ) {
            boolean isMatched = match(s.substring(1) , p.substring(1));
            isTrue[s.length()][p.length()] = isMatched;
            return isMatched;
        }
        else if( p.charAt(0) == '*' ){
            boolean isMatched = match( s.substring(0) , p.substring(1) );
            isTrue[s.length()][p.length()] = isMatched;
            if( isMatched == true ) return true;
    
            isMatched = match( s.substring(1) , p.substring(0) );
            isTrue[s.length()][p.length()] = isMatched;
            if( isMatched == true ) return true;
    
            isTrue[s.length()][p.length()] = false;
            return false;
        }
        else {
            isTrue[s.length()][p.length()] = false;
            return false;
        }
    }
    
    public boolean isMatch(String s,String p){
        isTrue = new boolean[s.length()+1][p.length()+1];
        visited = new boolean[s.length()+1][p.length()+1];
    
        visited[0][0] = true;
        isTrue[0][0] = true;
    
        for( int i = 1 ; i <= s.length() ; i ++ )
            for( int j = 1 ; j <= p.length() ; j ++ ) {
                isTrue[i][j] = false;
                visited[i][j] = false;
            }
        boolean result = match( s , p );
        return result;
    }
    

    }


Log in to reply
 

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