Three solutions for this question


  • 1
    L

    I used recursion, DP and DFS (with finite state machine).

    At first, we can optimize the regular string, such as "a*.bc*" equals to ".", "aaa' equals to "a*", so we can get the optimized string:

    private String optimize(final String p)
        {
            final StringBuilder sb = new StringBuilder();
            
            int i;
            for (i = 0; i < p.length() - 1; )
            {
                if (p.charAt(i + 1) == '*')
                {
                    char c = p.charAt(i);
                    boolean dot = '.' == c;
                    final StringBuilder sub = new StringBuilder();
                    int j;
                    for (j = i + 2; j + 1 < p.length() && p.charAt(j + 1) == '*'; j += 2)
                    {
                        dot = dot || p.charAt(j) == '.';
                        if (!dot)
                        {
                            if (p.charAt(j) != c)
                            {
                                sub.append(c);
                                sub.append('*');
                                c = p.charAt(j);
                            }
                        }
                    }
                    
                    if (dot)
                    {
                        sb.append(".*");
                    }
                    else
                    {
                        sb.append(sub.toString());
                        sb.append(c);
                        sb.append('*');
                    }
                    
                    i = j;
                }
                else
                {
                    sb.append(p.charAt(i++));
                }
            }
            
            sb.append(p.substring(i));
            
            return sb.toString();
        }
    

    Recursion version:

    private boolean helper(final String s, final int sp, final String p, final int pp)
        {
            if (sp >= s.length() && pp >= p.length())
            {
                return true;
            }
            else if (sp >= s.length())
            {
                int i;
                for (i = pp; i + 1 < p.length() && p.charAt(i + 1) == '*'; i += 2)
                {
                    
                }
                
                return i >= p.length();
            }
            else if (pp >= p.length())
            {
                return false;
            }
            
            
            if (pp + 1 < p.length() && p.charAt(pp + 1) == '*')
            {
                // 0
                if (helper(s, sp, p, pp + 2))
                {
                    return true;
                }
                else if (p.charAt(pp) == '.' || s.charAt(sp) == p.charAt(pp))
                {
                    return helper(s, sp + 1, p, pp) || helper(s, sp + 1, p, pp + 2);
                }
                else
                {
                    return false;
                }
            }
            else
            {
                return (p.charAt(pp) == '.' || s.charAt(sp) == p.charAt(pp)) && helper(s, sp + 1, p, pp + 1);
            }
        }
        
        public boolean isMatch(String s, String p)
        {
            return helper(s, 0, optimize(p), 0);
        }
    

    DP:

    public boolean isMatch(String s, String p)
    {
        p = optimize(p);
        
        final boolean[] current = new boolean[s.length() + 1];
        current[0] = true;
        
        for (int i = 0; i < p.length(); ++i)
        {
            final char c = p.charAt(i);
            if (i + 1 < p.length() && p.charAt(i + 1) == '*')
            {
                for (int j = 1; j < current.length; ++j)
                {
                    current[j] = current[j] || (current[j - 1] && ('.' == c || s.charAt(j - 1) == c));
                }
                ++i;
            }
            else
            {
                for (int j = current.length - 1; j > 0; --j)
                {
                    current[j] = current[j - 1] && ('.' == c || s.charAt(j - 1) == c);
                }
                
                current[0] = false;
            }
        }
        
        return current[current.length - 1];
    }
    

    DFS:

    private static class State
    {
        Map<Character, State> next = new HashMap<>();
    }
    
    private static class Data
    {
        final State state;
        final int pos;
        
        Data(final State state, final int pos)
        {
            this.state = state;
            this.pos = pos;
        }
    }
    
    private State build(final String p)
    {
        final State head = new State();
        State current = head;
        for (int i = 0; i < p.length(); ++i)
        {
            final State next = new State();
            if (i + 1 < p.length() && p.charAt(i + 1) == '*')
            {
                current.next.put(p.charAt(i++), current);
                current.next.put('*', next);
            }
            else
            {
                current.next.put(p.charAt(i), next);
            }
            
            current = next;
        }
        
        return head;
    }
    
    public boolean isMatch(String s, String p)
    {
        p = optimize(p);
        final State head = build(p);
        final Queue<Data> q = new LinkedList<>();
        q.offer(new Data(head, 0));
        
        while (!q.isEmpty())
        {
            final Data d = q.poll();
            if (d.pos >= s.length() && d.state.next.isEmpty())
            {
                return true;
            }
            else
            {
                if (d.pos < s.length())
                {
                    final char c = s.charAt(d.pos);
                    
                    if (d.state.next.containsKey(c))
                    {
                        q.offer(new Data(d.state.next.get(c), d.pos + 1));
                    }
                    else if (d.state.next.containsKey('.'))
                    {
                        q.offer(new Data(d.state.next.get('.'), d.pos + 1));
                    }
                }
                
                if (d.state.next.containsKey('*'))
                {
                    q.offer(new Data(d.state.next.get('*'), d.pos));
                }
            }
        }
        
        
        return false;
    }

  • 0
    T

    a small note:

    ur third solution is based on NFA, not DFA. as such it would potentially lead to exponential search space (which is of course the same as recursion). NFA conversion to DFA is pretty common but apparently very non-trivial in this context of a limited coding problem. take the example of aca

    this problem looks deceivingly simple as it begs you to try to use DFA, which would lead to a O(n) verification time given a string.


  • 0
    T

    This is simpler to read:
    basically this is backtracking. it searches down a decision tree, and the only point where there are multiple paths is x* in the pattern, where u can either try to consume a char in the string, or skip it (since the * includes 0 ). this basically comes down to the line in the following code that refer to the var "result"

        public class Solution {
    
    
    public boolean isMatch(String s, String p)
    {
        return matchRecursive(s.toCharArray(), 0, p.toCharArray(), 0    );
    }
    
    
    
    
    	public static boolean matchRecursive(char[] s, int ptr, char[] p, int ptrP) {
    		if (ptr == s.length && ptrP == p.length) return true;
    		
    		if (ptrP <= p.length-2 && p[ptrP+1] == '*') {
    			if (matchDigit(s,ptr,p,ptrP)) {
    			         boolean result = false;
    
    				// consume this digit, the * is still valid
    				result = matchRecursive(s, ptr+1, p, ptrP);
    			
    				if (result) return true;
    				// this digit can't align with pattern, have to ignore the * section
    				return matchRecursive(s, ptr, p, ptrP+2);
    			} else return matchRecursive(s, ptr, p, ptrP+2);
    			
    		}
    		else return matchDigit(s, ptr, p, ptrP) && matchRecursive(s, ptr+1, p, ptrP+1);
    	}
    	
    	public static boolean matchDigit(char[]s, int ptr, char[] p, int ptrP) {
    		if (ptr == s.length || ptrP == p.length ) return false;
    		if (p[ptrP] == '.') return true;
    		if (p[ptrP] == s[ptr]) return true;
    		return false;
    	}
    	
    }

Log in to reply
 

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