Java 4ms dp solution with O(n^2) time and O(n) space beats 95%


  • 13
    R

    The dp algorithm is known by many other solutions. An optimization is to reduce the storage to O(n) with only one row of data.

    public boolean isMatch(String s, String p) {
    		/**
    		 * This solution is assuming s has no regular expressions.
    		 * 
    		 * dp: res[i][j]=is s[0,...,i-1] matched with p[0,...,j-1];
    		 * 
    		 * If p[j-1]!='*', res[i][j] = res[i-1][j-1] &&
    		 * (s[i-1]==p[j-1]||p[j-1]=='.'). Otherwise, res[i][j] is true if
    		 * res[i][j-1] or res[i][j-2] or
    		 * res[i-1][j]&&(s[i-1]==p[j-2]||p[j-2]=='.'), and notice the third
    		 * 'or' case includes the first 'or'.
    		 * 
    		 * 
    		 * Boundaries: res[0][0]=true;//s=p="". res[i][0]=false, i>0.
    		 * res[0][j]=is p[0,...,j-1] empty, j>0, and so res[0][1]=false,
    		 * res[0][j]=p[j-1]=='*'&&res[0][j-2].
    		 * 
    		 * O(n) space is enough to store a row of res.
    		 */
    
    		int m = s.length(), n = p.length();
    		boolean[] res = new boolean[n + 1];
    		res[0] = true;
    
    		int i, j;
    		for (j = 2; j <= n; j++)
    			res[j] = res[j - 2] && p.charAt(j - 1) == '*';
    
    		char pc, sc, tc;
    		boolean pre, cur; // pre=res[i - 1][j - 1], cur=res[i-1][j]
    
    		for (i = 1; i <= m; i++) {
    			pre = res[0];
    			res[0] = false;
    			sc = s.charAt(i - 1);
    
    			for (j = 1; j <= n; j++) {
    				cur = res[j];
    				pc = p.charAt(j - 1);
    				if (pc != '*')
    					res[j] = pre && (sc == pc || pc == '.');
    				else {
    					// pc == '*' then it has a preceding char, i.e. j>1
    					tc = p.charAt(j - 2);
    					res[j] = res[j - 2] || (res[j] && (sc == tc || tc == '.'));
    				}
    				pre = cur;
    			}
    		}
    
    		return res[n];
    	}

  • 0
    C

    Very very very smart solution.


  • 0
    E

    But this cannot match "a." "ab" Do we have the assumption that s is a pure word?


  • 0
    W

    This solution has flaws.

    It could not handle some case like ("a", "*") (it crashes)


  • 0
    L

    Bralliant!!!!!!


  • 0
    R

    I've commented: This solution is assuming s has no regular expressions.


  • 0
    R

    well, the problem says: '' Matches zero or more of the preceding element. If my English is not that bad, I would believe '' must follow an element. Notice that our code is to solve a specific problem, not all problems. You may write an algorithm to EXTEND to solve a more general one.


  • 0
    R

    '*' (star) Matches zero or more of the preceding element.


  • 0

    Thank you, rikimberley.
    I have a question about your solution.
    Why we need this res[i][j] = res[i-1][j] ? What does res[i-1][j] mean?


  • 1
    B

    mark: run it against today's test data of leetcode on Sep 20.
    27 ms, beat 46%


Log in to reply
 

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