[刷题防痴呆] 0290 - 单词规律 (Word Patter

题目地址

https://leetcode.com/problems/word-pattern/description/

题目描述

290. Word Pattern

Given a pattern and a string str, find if str follows the same pattern.

Here follow means a full match, such that there is a bijection between a letter in pattern and a non-empty word in str.

Example 1:

Input: pattern = "abba", str = "dog cat cat dog"
Output: true
Example 2:

Input:pattern = "abba", str = "dog cat cat fish"
Output: false
Example 3:

Input: pattern = "aaaa", str = "dog cat cat dog"
Output: false
Example 4:

Input: pattern = "abba", str = "dog dog dog dog"
Output: false
Notes:
You may assume pattern contains only lowercase letters, and str contains lowercase letters that may be separated by a single space.

思路

• 用两个hashmap, 记录一一对应关系.

关键点

• 如果一开始word split的数组和pattern的length不相等, return false.
• 如果pattern -> word 不存在, word -> pattern 反而存在. return false.
• 如果pattern -> word 不存在, word -> pattern 也不存在. 进入map.
• 如果pattern -> word 存在, 看map里的word是不是和当前word相等.

代码

• 语言支持：Java

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

        Map<String, Character> wordMap = new HashMap<>();
        Map<Character, String> patternMap = new HashMap<>();
        String[] strs = s.split(" ");
        char[] sc = pattern.toCharArray();
        if (strs.length != sc.length) {
            return false;
        }

        for (int i = 0; i < strs.length; i++) {
            char c = sc[i];
            String word = strs[i];
            if (!wordMap.containsKey(word)) {
                wordMap.put(word, c);
            } else {
                if (!wordMap.get(word).equals(c)) {
                    return false;
                }
            }
            if (!patternMap.containsKey(c)) {
                patternMap.put(c, word);
            } else {
                if (!patternMap.get(c).equals(word)) {
                    return false;
                }
            }
        }

        return true;
    }
}