Leetcode 44) Wildcard Matching

18 Aug 2021 in Algorithms

Back To Back SWE’s Solution

https://yejip.com/algo/2021-05-13-LeetcodeStr139/

내 답안

class Solution {
    int[][] dp;

    public boolean isMatch(String s, String p) {
        dp = new int[s.length()+1][p.length()+1];


        //String[] pp=p.split("[?*]");System.out.println(Arrays.toString("a;b;c;d".split("((?<=;)|(?=;))")));
        return ismatch(s,p);

    }

    public boolean ismatch(String s, String p){
        if(dp[s.length()][p.length()]==-1){
            return false;
        }
        if(p.isEmpty() && s.isEmpty()){
            return true;
        }else if(p.isEmpty() && !s.isEmpty()){
            return false;
        }else if(!p.isEmpty() && s.isEmpty()){
            if(p.charAt(0)!='*'){
                return false;
            }else{
                if(p.length()>=1){
                    return ismatch(s,p.substring(1));
                }else{
                    return false;
                }

            }
        }

        if(s.equals(p)){return true;}

        if(p.charAt(0)!='*' && p.charAt(0)!='?'){
            if(p.charAt(0)!=s.charAt(0)){
                dp[s.length()][p.length()]=-1;
                return false;
            }else{
                return ismatch(s.substring(1),p.substring(1));
            }
        }
        if( p.charAt(0)=='?'){
            return ismatch(s.substring(1),p.substring(1));
        }
        String[] pp=p.split("(?<=/*/?)|(?=/*/?)");
        int i =0;
        while(i<pp.length && pp[i].equals("*")){
            i++;
            if(i==pp.length){
                return true;
            }
        }

        /*pp[i]=="?" 이래서 오류
        if(pp[i].equals("?")){
            if(i+1<=pp.length){
                //i+1이 맞을까? ㅇㅇ 문자열이 아니라 *나 ? 니까, 문자열처럼 뭉태기들은 여기에 포함이 안됨
                return isMatch(s.substring(0),p.substring(i+1));
            }
        }*/

        int l = pp[i].length();

        int j =0;
        while(j<s.length()){
            if(pp[i].equals("?")){
                if(ismatch(s.substring(j+1),p.substring(i+1))){
                    return true;
                }
            }
            j++;
        }
        j=0;
        while(j+l<=s.length()){
            if(pp[i].equals(s.substring(j,j+l)) ){
                if(ismatch(s.substring(j+l),p.substring(i+1))){
                    return true;
                }
            }
            j++;
        }
        dp[s.length()][p.length()]=-1;
        return false;
    }
}

다른 답안

class Solution {
    public boolean isMatch(String str, String pattern) {
        int s=0,p=0,match=0,starIdx=-1;

        while(s<str.length()){

            if(p<pattern.length() && (pattern.charAt(p)=='?' || pattern.charAt(p)==str.charAt(s))){
                s++;
                p++;
            }else if(p<pattern.length() && pattern.charAt(p)=='*'){
                starIdx=p;
                match=s;
                p++;
            }else if(starIdx!=-1){
                p=starIdx+1;
                match++;
                s=match;
            }
            else return false;
        }
        while(p<pattern.length() && pattern.charAt(p)=='*')
            p++;

        return p==pattern.length();
    }
}