290.单词规律

题目: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 中每个单词都被 单个空格 分隔

思路

为了判断字符串 s 是否遵循规律 pattern，可以采用哈希表来建立 pattern 中字符与 s 中单词之间的双向映射关系。如果 pattern 中的每个字符和 s 中的每个单词之间都能保持一一对应的关系，则字符串 s 遵循 pattern。

1. 将字符串 s 分割成单词数组：通过 split("\\s+") 方法将字符串 s 按照空格分隔成单词数组。
2. 检查长度是否匹配：如果 pattern 的长度和单词数组的长度不相等，直接返回 false。
3. 初始化哈希表：使用 charToWord 记录 pattern 中字符到单词的映射关系，使用 wordToChar 记录单词到 pattern 中字符的映射关系。
4. 遍历 pattern 和单词数组：通过遍历 pattern 和单词数组，检查并更新映射关系。如果发现映射关系不匹配，则返回 false。
5. 返回结果：如果所有字符和单词的映射关系都匹配，则返回 true。

• 时间复杂度:O(n)
• 空间复杂度:O(1)

代码

public boolean wordPattern(String pattern, String s) {
    // 将字符串 s 按空格分割成单词数组
    String[] words = s.split("\\s+");
    // 如果 pattern 的长度和单词数组的长度不相等，直接返回 false
    if (words.length != pattern.length()) {
        return false;
    }
    // 哈希表记录 pattern 中字符到单词的映射关系
    Map<Character, String> charToWord = new HashMap<>();
    // 哈希表记录单词到 pattern 中字符的映射关系
    Map<String, Character> wordToChar = new HashMap<>();

    for (int i = 0; i < pattern.length(); i++) {
        char c = pattern.charAt(i);
        // 检查 pattern -> 单词 的映射关系
        if (!charToWord.containsKey(c)) {
            // 更新映射关系
            charToWord.put(c, words[i]);
        } else {
            if (!charToWord.get(c).equals(words[i])) {
                // 映射关系不匹配
                return false;
            }
        }
    }
    // 检查 t -> s 的映射关系
    for (int i = 0; i < pattern.length(); i++) {
        char c = pattern.charAt(i);
        if (!wordToChar.containsKey(words[i])) {
            // 更新映射关系
            wordToChar.put(words[i], c);
        } else {
            if (wordToChar.get(words[i]) != c) {
                // 映射关系不匹配
                return false;
            }
        }
    }
    return true;
}