Leaky Cauldron
0%

单词规律

Posted on Edited on

LeetCode #290

单词规律

给定一种规律 pattern 和一个字符串 s ，判断 s 是否遵循相同的规律。

这里的 遵循 指完全匹配，例如， pattern 里的每个字母和字符串 s 中的每个非空单词之间存在着双向连接的对应规律。

示例1:

输入：pattern = “abba”, s = “dog cat cat dog”
输出：true

示例 2:

输入：pattern = “abba”, s = “dog cat cat fish”
输出：false

示例 3:

输入：pattern = “aaaa”, s = “dog cat cat dog”
输出：false

提示:

  • 1 <= pattern.length <= 300
  • pattern 只包含小写英文字母
  • 1 <= s.length <= 3000
  • s 只包含小写英文字母和 ' '
  • s 不包含 任何前导或尾随对空格
  • s 中每个单词都被 单个空格 分隔

题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public boolean wordPattern(String pattern, String s) {
        String[] splitStrs = s.split(" ");
        if (splitStrs.length != pattern.length()) return false;

        Map<Character, String> map = new HashMap<>();

        for (int i = 0; i < splitStrs.length; i++) {
            char ch = pattern.charAt(i);
            if (map.containsKey(ch)) {
                if (!splitStrs[i].equals(map.get(ch))) return false;
            } else if (map.containsValue(splitStrs[i])) return false;
            else map.put(ch, splitStrs[i]);
        }

        return true;
    }
}

LeetCode #291

单词规律 II

给你一种规律 pattern 和一个字符串 s，请你判断 s 是否和 pattern 的规律相匹配。

如果存在单个字符到字符串的 双射映射 ，那么字符串 s 匹配 pattern ，即：如果pattern 中的每个字符都被它映射到的字符串替换，那么最终的字符串则为 s 。双射 意味着映射双方一一对应，不会存在两个字符映射到同一个字符串，也不会存在一个字符分别映射到两个不同的字符串。

示例 1：

输入：pattern = “abab”, s = “redblueredblue”
输出：true
解释：一种可能的映射如下：
‘a’ -> “red”
‘b’ -> “blue”

示例 2：

输入：pattern = “aaaa”, s = “asdasdasdasd”
输出：true
解释：一种可能的映射如下：
‘a’ -> “asd”

示例 3：

输入：pattern = “aabb”, s = “xyzabcxzyabc”
输出：false

提示：

  • 1 <= pattern.length, s.length <= 20
  • pattern 和 s 由小写英文字母组成

题解

参考题解：@czwhl123

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
    Map<Character, String> map = new HashMap<>();

    public boolean wordPatternMatch(String pattern, String s) {
        // 边界条件，如果pattern读完了字符串也正好读完就true，如果字符串没读完就false
        if (pattern.length() == 0) return s.length() == 0;

        char ch = pattern.charAt(0);
        // 从 1 位开始尝试是否有映射，由于每个 pattern 至少得对应一个字符，
        // 所以如果字符串剩下的字符少于 pattern 剩下的字符数就可以停止循环了
        for (int i = 1; i <= s.length() - pattern.length() + 1; i++) {
            // mapS 是 ch 的映射，有则返回映射，没有则等于 null
            String subS = s.substring(0, i), mapS = map.get(ch);
            // 这个 pattern 有映射，并且等于这段字符；
            // 或者这段字符不是 pattern 的映射并且没有其他映射,
            // 则可以假设这个映射成立并继续尝试匹配剩下的字符
            if (subS.equals(mapS) || (mapS == null && !map.containsValue(subS))) {
                // 不管是否是正确答案，先放进 map 里面尝试
                map.put(ch, subS);
                // 如果正好对了就返回 true
                if (wordPatternMatch(pattern.substring(1), s.substring(i))) return true;
                // 如果不对那就把这个映射取消继续下一个循环进行尝试
                else if (mapS == null) map.remove(ch);
            }
        }
        return false;
    }
}