Word Pattern

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

Given apatternand a stringstr, find ifstrfollows the same pattern.

Herefollowmeans a full match, such that there is a bijection between a letter inpatternand anon-emptyword instr.

Notes: You may assumepatterncontains only lowercase letters, andstrcontains lowercase letters separated by a single space

Thoughts

和Isomorphic str一个套路。

Code

class Solution {
    public boolean wordPattern(String pattern, String str) {
        Map<Character, String> map = new HashMap<>();
        String[] words = str.split(" ");
        if (words.length != pattern.length()) {
            return false;
        }
        for (int i = 0; i < words.length; i++) {
            if (map.containsKey(pattern.charAt(i)) && !words[i].equals(map.get(pattern.charAt(i)))) {
                return false;
            } else if (!map.containsKey(pattern.charAt(i)) && map.containsValue(words[i])) {
                return false;
            }
            map.put(pattern.charAt(i), words[i]);
        }
        return true;
    }
}

Analysis

时间和空间复杂度都是O(n).