Two Pointers Non-DP Recursive Solution in Java


  • 0
    I

    Pass in two pointers si and pi at the initial position 0 and 0,

    1. If the characters on second pointer pi is *, recursively test the possible solution, as * may represent 0 or multiple characters
    2. If both positions' characters are the same (or character at pi is .), both of them ++
    public class Solution {
        public boolean isMatch(String s, String p) {
            return isMatch(s, 0, p, 0);
        }
        private boolean isMatch(String s, int si, String p, int pi) {
            if (pi == p.length()) return si == s.length();
            if (pi < p.length() - 1 && p.charAt(pi + 1) == '*') {
                /*
                '*' may represent 0 or multiple characters in s,
                so we keep increasing si and call the isMatch() method recursively to see if we can find a match to the end
                */
                while (si <= s.length() - 1 && (s.charAt(si) == p.charAt(pi) || p.charAt(pi) == '.')) {
                    if (isMatch(s, si, p, pi + 2)) return true;
                    si++;
                }
                /*
                Exit the while loop when:
                1. We cannot find matches, and si reaches s.length()
                2. We cannot reach a successful match to the end, but we find positions si and pi + 2 that have the same character
                */
                return isMatch(s, si, p, pi + 2);
            } else {
                return (si <= s.length() - 1 && s.charAt(si) == p.charAt(pi) || p.charAt(pi) == '.') && isMatch(s, si + 1, p, pi + 1);
            }
        }
    }
    

Log in to reply
 

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