Not DP Solution which drives me crazy


  • 0
    R
    public class Solution {
        public boolean isMatch(String s, String p) {
            return compare(s, p, 0, 0);
        }
        public boolean compare(String s, String p, int idxs, int idxp) {
            //System.out.println(s.length() + " " + idxs);
            while(idxs < s.length() && idxp < p.length()) {
                char a = s.charAt(idxs), b = p.charAt(idxp);
                if(idxp + 1 < p.length() && p.charAt(idxp + 1) == '*'){
                    idxp++;
                }else if (a == b || b == '.') {
                    idxs++;
                    idxp++;
                } else if(b != '*' ) {
                    return false;
                } else {
                    //check if still '*'
                    char starchar = p.charAt(idxp - 1);
                    while(idxp + 1 < p.length() && p.charAt(idxp + 1) == '*') idxp++;
                    //'*' is last character
                    if(idxp == p.length() - 1) {
                        if (starchar != '.') {
                            for(int i = idxs; i < s.length(); i++) {
                                if(s.charAt(i) != starchar) {
                                    return false;   
                                }
                            }
                        }
                        return true;
                    }
                    StringBuilder sb = new StringBuilder();
                    Deque<Character> queue = new ArrayDeque<>();
                    queue.offer(starchar);
                    int pcount = 0;
                    while(idxp + 2 < p.length() && p.charAt(idxp + 2) == '*') {
                            queue.offer(p.charAt(idxp + 1));
                            //System.out.println(p.charAt(idxp + 1));
                            idxp += 2;
                        }
                    while(idxp + 1 < p.length() && p.charAt(idxp + 1) != '*') {
                        if (p.charAt(idxp + 1) == '.'){
                            if(sb.length() != 0) break;
                            else {
                                while(idxp + 1 < p.length() && p.charAt(idxp + 1) == '.') {
                                    idxp++;
                                    pcount++;
                                }
                                continue;
                            }
                        }
                        if(idxp + 2 < p.length() && p.charAt(idxp + 2) == '*') break;
                        idxp++;
                        sb.append(p.charAt(idxp));
                    }
                    idxp++;
                    String pattern = sb.toString();
                    //System.out.println(pattern + " " + pcount + " " + idxs + " " + idxp);
                    int tmps = idxs;
                    if(pattern.length() == 0) {
                        int next = idxs;
                        while(next <= s.length() - pcount) {
                            //System.out.println("idxs: " + idxs + " next:" + next + " idxp: " + idxp + " pcount:" + pcount);
                            if (verify(s, idxs, next, queue) && compare(s, p, next + pcount, idxp)) return true;
                            next++;
                        }
                        return false;
                    }else {
                        tmps += pcount;
                        while(tmps < s.length()) {
                        int next = s.indexOf(pattern, tmps);
                        //System.out.println(next);
                        if (next == -1) return false;
                        if (verify(s, idxs, next, queue) && compare(s, p, next + pattern.length(), idxp)) return true;
                        tmps = next + 1;
                        }
                        return false;
                    }
                    
                }
            }
            if(idxs == s.length()) {
                while(idxp + 1 < p.length() && p.charAt(idxp + 1) == '*') {
                    idxp += 2;
                }
                if(idxp >= p.length()) return true;
            }
            
            return false;
        }
        public boolean verify(String str, int cur, int end, Deque<Character> queue) {
            if(queue.isEmpty()) return false;
            char starchar = queue.peek();
            if(starchar == '.' || cur == end) return true;
            if(str.charAt(cur) == starchar){
                if(cur == end - 1) return true;
                else return verify(str, cur + 1, end, queue);
            } else{
                queue.poll();
                return verify(str, cur, end, queue);
            }
        }
    }
    

Log in to reply
 

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