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

二、题目解析

三、参考代码

Python

class Solution:
    def wordPattern(self, pattern: str, s: str) -> bool:

        s = s.split()

        if len(pattern) != len(s):
            return False
        
        t = pattern

        # 接下来的逻辑和 LC205. 同构字符串 一模一样
        
        # 设置一个哈希集合用来存储字符串 s 当中的元素
        dic1 = {}

        # 设置一个哈希集合用来存储字符串 t 当中的元素
        dic2 = {}

        

        # 由于 t.length == s.length
        # 按照顺序访问 s 和 t 中对应的元素
        for i in range(len(pattern)):

            # 1、访问的元素 s[i] 存在于 dic1 中
            # 并且发现它对应的元素值和当前 t 中元素 t[i] 不相同
            # 返回 False
            if s[i] in dic1 and dic1[s[i]] != t[i]:
                return False

            # 2、访问的元素 t[i] 存在于 dic2 中
            # 并且发现它对应的元素值和当前 s 中元素 s[i] 不相同
            # 返回 False
            if t[i] in dic2 and dic2[t[i]] != s[i]:
                return False

            # 3、访问的元素 s[i] 不存在于 dic1 中
            # 存放到哈希集合中
            if s[i] not in dic1:
                # dic1[s[i]] = t[i]
                dic1[s[i]] = t[i]

            # 3、访问的元素 t[i] 不存在于 dic2 中
            # 存放到哈希集合中
            if t[i] not in dic2:
                # dic2[t[i]] = s[i]
                dic2[t[i]] = s[i]
        # 返回 True
        return True

Java

import java.util.HashMap;

class Solution {
    public boolean wordPattern(String pattern, String s) {

        // 将字符串 s 按照空格分割成数组
        String[] words = s.split(" ");

        // 如果 pattern 和分割后的数组长度不等，直接返回 false
        if (pattern.length() != words.length) {
            return false;
        }

        String t = pattern;

        // 接下来的逻辑和 LC205. 同构字符串 一模一样

        // 设置一个哈希表用来存储字符串 s 当中的元素
        HashMap<String, Character> dic1 = new HashMap<>();

        // 设置一个哈希表用来存储字符串 t 当中的元素
        HashMap<Character, String> dic2 = new HashMap<>();

        // 按照顺序访问 s 和 t 中对应的元素
        for (int i = 0; i < pattern.length(); i++) {

            // 获取当前字符和字符串单词
            String word = words[i];
            char ch = t.charAt(i);

            // 1、访问的元素 s[i] 存在于 dic1 中
            // 并且发现它对应的元素值和当前 t 中元素 t[i] 不相同
            // 返回 False
            if (dic1.containsKey(word) && dic1.get(word) != ch) {
                return false;
            }

            // 2、访问的元素 t[i] 存在于 dic2 中
            // 并且发现它对应的元素值和当前 s 中元素 s[i] 不相同
            // 返回 False
            if (dic2.containsKey(ch) && !dic2.get(ch).equals(word)) {
                return false;
            }

            // 3、访问的元素 s[i] 不存在于 dic1 中
            // 存放到哈希集合中
            if (!dic1.containsKey(word)) {
                dic1.put(word, ch);
            }

            // 3、访问的元素 t[i] 不存在于 dic2 中
            // 存放到哈希集合中
            if (!dic2.containsKey(ch)) {
                dic2.put(ch, word);
            }
        }
        // 返回 True
        return true;
    }
}

C++

class Solution {
public:
    bool wordPattern(string pattern, string s) {

        // 将字符串 s 按照空格分割成字符串数组
        vector<string> words;
        stringstream ss(s);
        string word;
        while (ss >> word) {
            words.push_back(word);
        }

        // 如果 pattern 和分割后的数组长度不等，直接返回 false
        if (pattern.size() != words.size()) {
            return false;
        }

        // 设置一个哈希表用来存储字符串 s 当中的元素
        unordered_map<string, char> dic1;

        // 设置一个哈希表用来存储字符串 t 当中的元素
        unordered_map<char, string> dic2;

        // 按照顺序访问 s 和 t 中对应的元素
        for (int i = 0; i < pattern.size(); i++) {

            string cur_word = words[i];
            char cur_char = pattern[i];

            // 1、访问的元素 s[i] 存在于 dic1 中
            // 并且发现它对应的元素值和当前 t 中元素 t[i] 不相同
            // 返回 False
            if (dic1.count(cur_word) && dic1[cur_word] != cur_char) {
                return false;
            }

            // 2、访问的元素 t[i] 存在于 dic2 中
            // 并且发现它对应的元素值和当前 s 中元素 s[i] 不相同
            // 返回 False
            if (dic2.count(cur_char) && dic2[cur_char] != cur_word) {
                return false;
            }

            // 3、访问的元素 s[i] 不存在于 dic1 中
            // 存放到哈希集合中
            if (!dic1.count(cur_word)) {
                dic1[cur_word] = cur_char;
            }

            // 3、访问的元素 t[i] 不存在于 dic2 中
            // 存放到哈希集合中
            if (!dic2.count(cur_char)) {
                dic2[cur_char] = cur_word;
            }
        }
        // 返回 True
        return true;
    }
};