题目：
给你一个字符串 s 和一个字符规律 p，请你来实现一个支持 '.' 和 '*' 的正则表达式匹配。
'.' 匹配任意单个字符
'*' 匹配零个或多个前面的那一个元素
所谓匹配，是要涵盖 整个 字符串 s的，而不是部分字符串。
示例 1：
输入：s = "aa", p = "a"
输出：false
解释："a" 无法匹配 "aa" 整个字符串。
示例 2:
输入：s = "aa", p = "a*"
输出：true
解释：因为 '*' 代表可以匹配零个或多个前面的那一个元素, 在这里前面的元素就是 'a'。因此，字符串 "aa" 可被视为 'a' 重复了一次。
示例 3：
输入：s = "ab", p = ".*"
输出：true
解释：".*" 表示可匹配零个或多个（'*'）任意字符（'.'）。
思路：
设table[i][j]表示 s 的前 i 个字符与 p 中的前 j 个字符是否能够匹配，针对不同的情况见注释
代码(java)
1. class Solution { 2. public boolean isMatch(String s, String p) { 3. boolean table[][] = new boolean[s.length() +1][p.length()+1]; 4. //两个空字符串可以匹配 5. table[0][0]=true; 6. 7. //预处理，处理table的第一行，第一列除了table[0][0]之外都是0，不需要额外处理 8. for(int col=1;col<table[0].length;col++){ 9. //因为table的长和宽都比题目给定的s和p大1 10. //所以table[0][col]对应的其实是s为空字符串，p在col-1的字符 11. char ch=p.charAt(col-1); 12. 13. if(col>1){ 14. if(ch=='*'){ 15. //table[0][col]的值由前2个的值决定 16. //因为*之前的数字可以出现0次,所以s=''和A*这样的p是匹配的 17. table[0][col]=table[0][col-2]; 18. } else{ 19. table[0][col]=false; 20. } 21. }else{// ''和*也是匹配的 22. if( ch=='*' ){ 23. table[0][col]=true; 24. } 25. } 26. } 27. 28. //打表 29. for(int row=1;row<table.length;row++){ 30. char ch1=s.charAt(row-1); 31. for(int col=1;col<table[row].length;col++){ 32. char ch2=p.charAt(col-1); 33. //如果p[j]和s[i]相同,或者p[j]为'.'，则当前状态由左上角决定 34. if(ch1==ch2 || ch2=='.'){ 35. table[row][col]=table[row-1][col-1]; 36. }else if(ch2=='*'){ 37. if(col>1){ 38. //因为*之前的字符可以出现0次,所以类似s=x和xA*这样的p是匹配的 39. //则table[row][col]的状态与table[row][col-2]一致 40. if(table[row][col-2]){ 41. table[row][col]=true; 42. }else{ 43. char prev=p.charAt(col-2); 44. //例如AAA和A*这种情况，比 45. //较s的最后一个字符与p的*前的一个字符是否相等， 46. //如果相等，那此时他的值就等于AA和A*的的值 47. if(prev==ch1 || prev=='.'){ 48. table[row][col] = table[row-1][col]; 49. } 50. } 51. } 52. } 53. } 54. } 55. 56. //返回右下角的最后的值 57. return table[table.length-1][table[0].length-1]; 58. 59. 60. } 61. }
