fibers
diff --git a/‎src/main/java/com/fibers/algorithm/leetcode/_10/Solution.java
Lines changed: 9 additions & 11 deletions b/‎src/main/java/com/fibers/algorithm/leetcode/_10/Solution.java
Lines changed: 9 additions & 11 deletions
@@ -1,16 +1,16 @@
 package com.fibers.algorithm.leetcode._10;
+
 /*
  * @lc app=leetcode.cn id=10 lang=java
  *
  * [10] 正则表达式匹配
  */
-
 // @lc code=start
 class Solution {
 
     public static void main(String[] args) {
         Solution s = new Solution();
-        s.isMatch("aa", "a*");
+        System.out.println(s.isMatch("ab", ".*"));
     }
 
     public boolean isMatch(String s, String p) {
@@ -24,25 +24,23 @@ public boolean isMatch(String s, String p) {
         boolean dp[][] = new boolean[sLen + 1][pLen + 1];
         dp[0][0] = true;
 
-        if (p.charAt(0) == '.' || p.charAt(0) == s.charAt(0)) {
-            dp[1][1] = true;
+        for (int j = 2; j <= pLen; j++) {
+            dp[0][j] = dp[0][j - 2] && p.charAt(j - 1) == '*';
         }
 
         for (int i = 1; i <= sLen; i++) {
             for (int j = 1; j <= pLen; j++) {
-                if (s.charAt(i) == p.charAt(j) || p.charAt(j) == '.') {
+                if (s.charAt(i - 1) == p.charAt(j - 1) || p.charAt(j - 1) == '.') {
                     dp[i][j] = dp[i - 1][j - 1];
-                } else if (p.charAt(j) == '*') {
-                    // abcc* match acb, as c* count as empty
-                    if (p.charAt(j - 1) != s.charAt(i)) {
+                } else if (p.charAt(j - 1) == '*') {
+                        dp[i][j] = dp[i - 1][j] || dp[i][j - 1] || dp[i][j - 2];
+                    } else if (p.charAt(j - 2) != s.charAt(i - 1)) {
                         dp[i][j] = dp[i][j - 2];
-                    } else if (p.charAt(j - 1) == s.charAt(i) || p.charAt(j - 1) == '.') {
-                        dp[i][j] = dp[i - 1][j] || dp[i][j - 1];
                     }
                 }
             }
         }
-
         return dp[sLen][pLen];
     }
 }
Original file line number	Diff line number	Diff line change
`@@ -1,16 +1,16 @@`
`1`	`1`	`package com.fibers.algorithm.leetcode._10;`
	`2`	`+`
`2`	`3`	`/*`
`3`	`4`	`* @lc app=leetcode.cn id=10 lang=java`
`4`	`5`	`*`
`5`	`6`	`* [10] 正则表达式匹配`
`6`	`7`	`*/`
`7`		`-`
`8`	`8`	`// @lc code=start`
`9`	`9`	`class Solution {`
`10`	`10`
`11`	`11`	`public static void main(String[] args) {`
`12`	`12`	`Solution s = new Solution();`
`13`		`- s.isMatch("aa", "a*");`
	`13`	`+ System.out.println(s.isMatch("ab", ".*"));`
`14`	`14`	`}`
`15`
`16`	`16`	`public boolean isMatch(String s, String p) {`
`@@ -24,25 +24,23 @@ public boolean isMatch(String s, String p) {`
`24`	`24`	`boolean dp[][] = new boolean[sLen + 1][pLen + 1];`
`25`	`25`	`dp[0][0] = true;`
`26`	`26`
`27`		`- if (p.charAt(0) == '.' \|\| p.charAt(0) == s.charAt(0)) {`
`28`		`- dp[1][1] = true;`
	`27`	`+ for (int j = 2; j <= pLen; j++) {`
	`28`	`+ dp[0][j] = dp[0][j - 2] && p.charAt(j - 1) == '*';`
`29`	`29`	`}`
`30`	`30`
`31`	`31`	`for (int i = 1; i <= sLen; i++) {`
`32`	`32`	`for (int j = 1; j <= pLen; j++) {`
`33`		`- if (s.charAt(i) == p.charAt(j) \|\| p.charAt(j) == '.') {`
	`33`	`+ if (s.charAt(i - 1) == p.charAt(j - 1) \|\| p.charAt(j - 1) == '.') {`
`34`	`34`	`dp[i][j] = dp[i - 1][j - 1];`
`35`		`- } else if (p.charAt(j) == '*') {`
`36`		`- // abcc* match acb, as c* count as empty`
`37`		`- if (p.charAt(j - 1) != s.charAt(i)) {`
	`35`	`+ } else if (p.charAt(j - 1) == '*') {`
	`36`	`+ if (p.charAt(j - 2) == s.charAt(i - 1) \|\| p.charAt(j - 2) == '.') {`
	`37`	`+ dp[i][j] = dp[i - 1][j] \|\| dp[i][j - 1] \|\| dp[i][j - 2];`
	`38`	`+ } else if (p.charAt(j - 2) != s.charAt(i - 1)) {`
`38`	`39`	`dp[i][j] = dp[i][j - 2];`
`39`		`- } else if (p.charAt(j - 1) == s.charAt(i) \|\| p.charAt(j - 1) == '.') {`
`40`		`- dp[i][j] = dp[i - 1][j] \|\| dp[i][j - 1];`
`41`	`40`	`}`
`42`	`41`	`}`
`43`	`42`	`}`
`44`	`43`	`}`
`45`		`-`
`46`	`44`	`return dp[sLen][pLen];`
`47`	`45`	`}`
`48`	`46`	`}`