Leetcode 10) Regular Expression Matching

20 Aug 2021 in Algorithms

• 문제 이해를 잘못해서 삽질함.

와일드 카드와 레귤러 익스프레션은 다른 것. 면접장에서 삽질하는 것보다 훨씬 낫지..

내 답안

class Solution {
    int[][] dp;
    public boolean isMatch(String s, String p) {
        dp= new int[s.length()+1][p.length()+1];
        for(int[] dpdp : dp){
            Arrays.fill(dpdp,0);
        }
        return rem(s,p);
    }
    
    public boolean rem(String s, String p ){
        int sLen = s.length();
        int pLen = p.length();
        
        //memoization 에 의한 base
        if(dp[sLen][pLen]==1){
            return true;
        }else if(dp[sLen][pLen]==-1){
            return false;
        }
        
        //그냥 함수의 base
        if(sLen==0 && pLen==0){
            return true;
        }else if(pLen==0){
            return false;
        }else if(sLen==0){
            int end = p.length();
            if(p.charAt(end-1)=='*'){
                return rem(s,p.substring(0,end-2));
            }else{
                return false;
            }
        }
        
        if(p.charAt(pLen-1)=='.'){
            boolean test = rem(s.substring(0,sLen-1),p.substring(0,pLen-1));
            if(test){
                dp[sLen][pLen]=1;
            }else{
                dp[sLen][pLen]=-1;
            }
            return test;
        }

        
        
        if(p.charAt(pLen-1)=='*'){
            boolean test = rem(s,p.substring(0,pLen-2));
            if(test){
                dp[sLen][pLen]=1;
                return true;}
            
            char target = p.charAt(pLen-2);
            
            int i = sLen-1;
            while(i>=0 && (target == s.charAt(i) ||target == '.')){
                test = rem(s.substring(0,i),p.substring(0,pLen-2));
                if(test){
                    dp[i+1][pLen]=1;
                    return true;
                }
                i--;
            }
            dp[sLen][pLen]=-1;
            return false;
           
        }
        
        
        if(p.charAt(pLen-1)==s.charAt(sLen-1)){
            boolean test=rem(s.substring(0,sLen-1),p.substring(0,pLen-1));
            if(test){
                dp[sLen][pLen]=1;
            }else{
                dp[sLen][pLen]=-1;
            }
            return test;
        }else{
            dp[sLen][pLen]=-1;
            return false;
        }
                     
}
}

다른 답안

class Solution {
    public boolean isMatch(String s, String p) {
        boolean[][] match = new boolean[s.length()+1][p.length()+1];
        match[0][0] = true;

        for (int i = 1; i<= p.length(); i++) {
            if (p.charAt(i-1) == '*') {
                match[0][i] = match[0][i-2];
            }
        }

        for (int i = 1; i <= s.length(); i++) {
            for (int j = 1; j <= p.length(); j++) {
                char cp = p.charAt(j-1);
                if (cp == '.' || cp == s.charAt(i-1)) {
                    match[i][j] = match[i-1][j-1];
                } else if (cp == '*') {
                    char cp_1 = p.charAt(j-2);
                    if (cp_1 == '.' || cp_1 ==  s.charAt(i-1)) {
                        match[i][j] = match[i][j-2] || match[i-1][j];
                    } else {
                        match[i][j] = match[i][j-2];
                    }                    
                }
            }
        }
        return match[s.length()][p.length()];
    }
}

삽질

class Solution {
    boolean[][] dp;
    public boolean isMatch(String s, String p) {
        dp= new boolean[s.length()+1][p.length()+1];
        return rem(s,p);
    }

    public boolean rem(String s, String p ){
        //base case?
        int ls = s.length();
        int lp = p.length();
        //0일때 어떻게 처리할건지?
        if(lp==0 && ls!=0){
            dp[ls][lp]=false;
            return false;
        }
        /*
                if(s.charAt(0)==p.charAt(0)){
            return rem(s.substring(1),p.substring(1));
        }
        이 코드를 앞에다 놓으면, "" , "a"일때 처리가 안되니까 뒤로 뺀다. 
        하드코딩하려고하면, "","*" 일 때 문제가 생기니까. 뒤로 뺴기. 
        "", "."이럴때도 커버되나? 
    */

        if(p.charAt(0)=='.' || p.charAt(0)==s.charAt(0)){
            dp[ls][lp] = true; //return true하면 그 문자열 전체가 맞다는 의미가 되니까, 그렇게 하지는 못하고 dp에 true를 저장하므로써, 적어도 끝에 한자리 비교했을때는 맞으니까 계속 가라 라는 의미를 저장해 놓을 수 있다.
            return rem(s.substring(1),p.substring(1));
        }

        //* 일때가 약간 복잡한데 괜찮다. 풀 수 있음.
        int i =0;
        //.와 *가 여러개 있을 때는 어떻게 할까??
        //.와 *가아닐때 까지 돌려주면 될듯?
        int j=0;
        //여기서 .. 이런 케이스는 어차피 처리되지 않는다. 앞에서 컷당함. *. 이 케이스가 처리된다.
        while(j<lp && (p.charAt(j)=='*'||p.charAt(j)=='.')){
            j++;
            if(j==lp){
                return true; //마지막은 어떤 시퀀스가 와도 완전 상관없게 되는거니까.
            }
        }
        //j조건 안에서 확인했으니까, 여기 나온 j는 무조건 범위안 j가된다.

        //p에 *이 담겨있으니까, while 문 조건에 들어갈 것은 s다.
        while(i<ls){
            if(s.charAt(i)==p.charAt(j)){
                //맞으면 그다음 시퀀스로 탐방가보기 , 여기 i+1에서 문제가 생길 수도 있겠다.
                boolean tr = rem(s.substring(i+1), p.substring(j+1));
                dp[i][j] = tr;
                if(tr){
                    return true;
                }
            }
            i++;
        }
        if(s.charAt(0)==p.charAt(0)){
            return rem(s.substring(1),p.substring(1));
        }else{
            dp[ls][lp]=false;
            return false;
        }

    }
}