[Leetcode] Regular Expression Matching 正则表达式匹配
Regular Expression Matching
动态规划复杂度时间 O(NM) 空间 O(N) 思路这道题可以用递归解决,不过时间复杂度是指数级,这里介绍一个用动态规划在平方时间内解决的办法。 那我们就可以从后往前开始看pattern的每一位能匹配多少string的字符了:
我们举个例子 match: 0 0 0 1 string: a a b pattern: a * b | 这里我们先看pattern最后一位b能匹配到多少,这里因为b不是星号,所以我们从左往右尝试匹配string,第一个a不行,第二个a也不行,然后到b,这里因为 match: 0 0 1 1 string: a a b pattern: a * b | 然后看pattern的这个星号,我们要从后往前匹配string。因为b已经被匹配了, 这里还有几个情况,首先,无论刚才那pattern中最后一个b有没有匹配到string中任何一个字符, 代码public class Solution { public boolean isMatch(String s,String p) { boolean[] match = new boolean[s.length() + 1]; match[s.length()] = true; for(int i = p.length() - 1; i >=0; i--){ if(p.charAt(i) == '*'){ // 如果是星号,从后往前匹配 for(int j = s.length() - 1; j >= 0; j--){ match[j] = match[j] || (match[j + 1] && (p.charAt(i - 1) == '.' || (p.charAt(i - 1) == s.charAt(j)))); } // 记得把i多减一,因为星号是和其前面的字符配合使用的 i--; } else { // 如果不是星号,从前往后匹配 for(int j = 0; j < s.length(); j++){ match[j] = match[j + 1] && (p.charAt(i) == '.' || (p.charAt(i) == s.charAt(j))); } // 只要试过了pattern中最后一个字符,就要把match[s.length()]置为false match[s.length()] = false; } } return match[0]; } } (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |