dfs 正则表达式

192. 通配符匹配

中文

English

判断两个可能包含通配符“？”和“*”的字符串是否匹配。匹配规则如下：

'?' 可以匹配任何单个字符。
'*' 可以匹配任意字符串（包括空字符串）。

两个串完全匹配才算匹配成功。

样例

样例1

输入:

"aa"

"a"

输出: false

输出2

输入:

"aa"

"aa"

输出: true

输出3

输入:

"aaa"

"aa"

输出: false

输出4

输入:

"aa"

"*"

输出: true

说明: '*' 可以替换任何字符串

输出5

输入:

"aa"

"a*"

输出: true

样例6

输入:

"ab"

"?*"

输出: true

说明: '?' -> 'a' '*' -> 'b'

样例7

输入:

"aab"

"c*a*b"

输出: false

class Solution:

    """

    @param s: A string

    @param p: A string includes "?" and "*"

    @return: is Match?

    """

    def isMatch(self, s, p):

        # write your code here

        self.cache = {}

        return self.helper(s, p, s_at=len(s)-1, p_at=len(p)-1)

    def helper(self, s, p, s_at, p_at):

        if (s_at, p_at) in self.cache:

            return self.cache[(s_at, p_at)]

        if p_at < 0:

            return s_at < 0

        if s_at < 0:

            for i in range(0, p_at+1):

                if p[i] != "*":

                    return False

            return True

        if p[p_at] == '?':

            is_match = self.helper(s, p, s_at-1, p_at-1)

        elif p[p_at] == '*':

            is_match = self.helper(s, p, s_at-1, p_at) or \

                    self.helper(s, p, s_at, p_at-1)

        else:

            is_match = s_at >= 0 and s[s_at]==p[p_at] and \

                   self.helper(s, p, s_at-1, p_at-1)

        self.cache[(s_at, p_at)] = is_match

        return is_match

注意如果不用cache的话会超时。

更复杂一点的题目：

154. 正则表达式匹配

中文

English

实现支持'.'和'*'的正则表达式匹配。

'.'匹配任意一个字母。

'*'匹配零个或者多个前面的元素。

匹配应该覆盖整个输入字符串，而不仅仅是一部分。

需要实现的函数是：bool isMatch(string s, string p)

isMatch("aa","a") → false

isMatch("aa","aa") → true

isMatch("aaa","aa") → false

isMatch("aa", "a*") → true

isMatch("aa", ".*") → true

isMatch("ab", ".*") → true

isMatch("aab", "c*a*b") → true

样例

样例 1:

输入："aa"，"a"

输出：false

解释：

无法匹配

样例 2:

输入："aa"，"a*"

输出：true

解释：

'*' 可以重复 a

class Solution:

    """

    @param s: A string

    @param p: A string includes "." and "*"

    @return: A boolean

    """

    def isMatch(self, s, p):

        # write your code here

        self.cache = {}

        return self.helper(s, p, s_at=len(s)-1, p_at=len(p)-1)

    def helper(self, s, p, s_at, p_at):

        if (s_at, p_at) in self.cache:

            return self.cache[(s_at, p_at)]

        if p_at < 0:

            return s_at < 0

        else:

            if s_at < 0:

                for i in range(p_at, -1, -2):

                    if p[i] != '*':

                        return False

                return True

        if p[p_at] == '.':

            is_match = self.helper(s, p, s_at-1, p_at-1)

        elif p[p_at] == '*':

            matched_once = (p_at > 0 and (p[p_at-1] == '.' or p[p_at-1] == s[s_at])) and \

                self.helper(s, p, s_at-1, p_at)

            matched_none = self.helper(s, p, s_at, p_at-2)

            is_match = matched_once or matched_none

        else:

            is_match = s_at >= 0 and s[s_at]==p[p_at] and \

                   self.helper(s, p, s_at-1, p_at-1)

        self.cache[(s_at, p_at)] = is_match

        return is_match

算法思路整体上和上面题目一样，唯一的区别就是pattern -2，还有对于空串的匹配截止条件。

"" 匹配类似"a*b*c*"这样的模式。

当然，从前往后的匹配解法也是可以的，也就是匹配的时候pattern往前多看一步看是不是*来决定走一步还是走两步，参考代码：

class Solution:

    """

    @param s: A string

    @param p: A string includes "?" and "*"

    @return: is Match?

    """

    def isMatch(self, source, pattern):

        return self.is_match_helper(source, 0, pattern, 0, {})

    # source 从 i 开始的后缀能否匹配上 pattern 从 j 开始的后缀

    # 能 return True

    def is_match_helper(self, source, i, pattern, j, memo):

        if (i, j) in memo:

            return memo[(i, j)]

        # source is empty

        if len(source) == i:

            return self.is_empty(pattern[j:])

        if len(pattern) == j:

            return False

        if j + 1 < len(pattern) and pattern[j + 1] == '*':

            matched = self.is_match_char(source[i], pattern[j]) and self.is_match_helper(source, i + 1, pattern, j, memo) or \

                self.is_match_helper(source, i, pattern, j + 2, memo)

        else:

            matched = self.is_match_char(source[i], pattern[j]) and \

                self.is_match_helper(source, i + 1, pattern, j + 1, memo)

        memo[(i, j)] = matched

        return matched

    def is_match_char(self, s, p):

        return s == p or p == '.'

    def is_empty(self, pattern):

        if len(pattern) % 2 == 1:

            return False

        for i in range(len(pattern) // 2):

            if pattern[i * 2 + 1] != '*':

                return False

        return True

829. 字模式 II

中文

English

给定一个pattern和一个字符串str，查找str是否遵循相同的模式。
这里遵循的意思是一个完整的匹配，在一个字母的模式和一个非空的单词str之间有一个双向连接的模式对应。(如果a对应s，那么b不对应s。例如，给定的模式= "ab"， str = "ss"，返回false）。

样例

样例1

输入:

pattern = "abab"

str = "redblueredblue"

输出: true

说明: "a"->"red","b"->"blue"

样例2

输入:

pattern = "aaaa"

str = "asdasdasdasd"

输出: true

说明: "a"->"asd"

样例3

输入:

pattern = "aabb"

str = "xyzabcxzyabc"

输出: false

注意事项

您可以假设模式和str只包含小写字母

class Solution:

    """

    @param pattern: a string,denote pattern string

    @param str: a string, denote matching string

    @return: a boolean

    """

    def wordPatternMatch(self, pattern, str):

        # write your code here

        self.word_dict = {}

        self.word_match = {}

        return self.dfs(pattern, str)

    def dfs(self, pattern, s):

        if not pattern:

            return not s

        if not s:

            return not pattern

        pattern_char = pattern[0]

        if pattern_char in self.word_dict:

            word_to_match = self.word_dict[pattern_char]

            return s[:len(word_to_match)] == word_to_match and \

                self.dfs(pattern[1:], s[len(word_to_match):])

        else:

            for i in range(0, len(s)):

                word = s[:i+1]

                if word in self.word_match:

                    continue

                self.word_dict[pattern_char] = word

                self.word_match[word] = pattern_char

                if self.dfs(pattern[1:], s[i+1:]):

                    return True

                del self.word_dict[pattern_char]

                del self.word_match[word]

            return False

    """

         这里我们为什么需要一个额外的 Set<String> 呢？ 

			一个好的测试用例是:

			pattern:    "bdpbibletwuwbvh"

			str:        "aaaaaaaaaaaaaaa"

		 这里第一次执行时， map中匹配了 b -> a

		 递归进去以后第二次执行时，d 没有在 map 中，所以跳过了map的匹配检测，

		 所以进入循环体， 这时第二个word 又是 a, 按道理 a 应该被 b 匹配并且之前应该在map.containsKey的检查中跳出， 但现在并没有跳出，而是试图绑匹配给另一个pattern的字母 d,

		 很明显 b != d 重复绑定不是正确结果， 所以需要continue掉这次尝试。

    """

巴特西

dfs 正则表达式

192. 通配符匹配

样例

154. 正则表达式匹配

样例

829. 字模式 II

样例

注意事项

最新文章

热门文章