Easy

题目描述

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

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

  • pattern 中的每个字母都映射到 s 中的一个唯一单词。
  • s 中的每个唯一单词都映射到 pattern 中的一个字母。
  • 不能有两个字母映射到同一个单词，也不能有两个单词映射到同一个字母。

示例 1:

输入: pattern = "abba", s = "dog cat cat dog"
输出: true
解释:
双射可以按如下方式建立:
'a' 映射到 "dog"。
'b' 映射到 "cat"。

示例 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. 首先将字符串 s 按空格分割成单词数组
  2. 检查模式字符串长度与单词数组长度是否相等，不等则直接返回 false
  3. 使用两个哈希表：
    • charToWord: 存储字符到单词的映射
    • wordToChar: 存储单词到字符的映射
  4. 遍历模式字符串和单词数组：
    • 如果字符已存在映射，检查是否映射到当前单词
    • 如果单词已存在映射，检查是否映射到当前字符
    • 如果都不存在映射，建立新的双向映射
    • 任何冲突都返回 false
  5. 遍历完成后返回 true

时间复杂度分析： 需要遍历一次模式字符串，每次哈希表操作为 O(1)，总体为 O(n)。 空间复杂度分析： 需要存储两个哈希表和分割后的单词数组，为 O(n)。

代码实现

class Solution {
public:
    bool wordPattern(string pattern, string s) {
        vector<string> words;
        stringstream ss(s);
        string word;
        while (ss >> word) {
            words.push_back(word);
        }
        
        if (pattern.length() != words.size()) {
            return false;
        }
        
        unordered_map<char, string> charToWord;
        unordered_map<string, char> wordToChar;
        
        for (int i = 0; i < pattern.length(); i++) {
            char c = pattern[i];
            string w = words[i];
            
            if (charToWord.count(c)) {
                if (charToWord[c] != w) {
                    return false;
                }
            } else {
                charToWord[c] = w;
            }
            
            if (wordToChar.count(w)) {
                if (wordToChar[w] != c) {
                    return false;
                }
            } else {
                wordToChar[w] = c;
            }
        }
        
        return true;
    }
};

class Solution:
    def wordPattern(self, pattern: str, s: str) -> bool:
        words = s.split()
        
        if len(pattern) != len(words):
            return False
        
        char_to_word = {}
        word_to_char = {}
        
        for i in range(len(pattern)):
            c = pattern[i]
            w = words[i]
            
            if c in char_to_word:
                if char_to_word[c] != w:
                    return False
            else:
                char_to_word[c] = w
            
            if w in word_to_char:
                if word_to_char[w] != c:
                    return False
            else:
                word_to_char[w] = c
        
        return True

public class Solution {
    public bool WordPattern(string pattern, string s) {
        string[] words = s.Split(' ');
        
        if (pattern.Length != words.Length) {
            return false;
        }
        
        Dictionary<char, string> charToWord = new Dictionary<char, string>();
        Dictionary<string, char> wordToChar = new Dictionary<string, char>();
        
        for (int i = 0; i < pattern.Length; i++) {
            char c = pattern[i];
            string w = words[i];
            
            if (charToWord.ContainsKey(c)) {
                if (charToWord[c] != w) {
                    return false;
                }
            } else {
                charToWord[c] = w;
            }
            
            if (wordToChar.ContainsKey(w)) {
                if (wordToChar[w] != c) {
                    return false;
                }
            } else {
                wordToChar[w] = c;
            }
        }
        
        return true;
    }
}

var wordPattern = function(pattern, s) {
    const words = s.split(' ');
    
    if (pattern.length !== words.length) {
        return false;
    }
    
    const charToWord = new Map();
    const wordToChar = new Map();
    
    for (let i = 0; i < pattern.length; i++) {
        const c = pattern[i];
        const w = words[i];
        
        if (charToWord.has(c)) {
            if (charToWord.get(c) !== w) {
                return false;
            }
        } else {
            charToWord.set(c, w);
        }
        
        if (wordToChar.has(w)) {
            if (wordToChar.get(w) !== c) {
                return false;
            }
        } else {
            wordToChar.set(w, c);
        }
    }
    
    return true;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度大小
时间复杂度O(n)
空间复杂度O(n)

其中 n 为模式字符串的长度。时间复杂度主要来自于遍历模式字符串和单词数组，空间复杂度主要来自于存储两个哈希表和分割后的单词数组。

相关题目