Java super slow memory search solution


  • 0
    Z

    public class Solution {
    public boolean isMatch(String s, String p) {
    int len1 = s.length() , len2 = p.length();

        if(len2 == 1 && p.charAt(0) == '*')
            return true;
        
        boolean[][] flag = new boolean[len1 + 1][len2 + 1];
        boolean[][] valid = new boolean[len1 + 1][len2 + 1];
        
        flag[0][0] = true;
        valid[0][0] = true;
        
        memory(flag , valid , len1 , len2 , s.toCharArray() , p.toCharArray());
        
        return valid[len1][len2];
    }
    
    public boolean memory(boolean[][] flag , boolean[][] valid , int i1, int i2 , char[] source , char[] target){
        
        if(flag[i1][i2]) {
            return valid[i1][i2];
        }
        
        if(i2 == 0) {
            return false;
        } else if(i1 == 0) {
            for(int i = i2;i>0;i--) {
                if(target[i-1] != '*') {
                    return false;
                }
            }
            return true;
        }
        
        flag[i1][i2] = true;
        
        if(target[i2-1] == '?') {
            valid[i1][i2] = memory(flag , valid , i1-1,i2-1 , source , target);
        } else if(target[i2-1] == '*') {
            for(int i = i1;i>=0;i--) {
                if(memory(flag , valid , i , i2-1 , source , target)) {
                    valid[i1][i2] = true;
                    break;
                }
            }
        } else {
            if(source[i1-1] == target[i2-1]) {
                valid[i1][i2] = memory(flag , valid , i1-1,i2-1 , source , target);
            } else {
                return false;
            }
        }
        
        return valid[i1][i2];
    }
    

    }


Log in to reply
 

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