Question
Formatted question description: https://leetcode.ca/all/290.html
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.
Algorithm
If the one-to-one mapping cannot be established, return false directly.
It also returns false when the mapping values of the two HashMaps are not the same.
Code
Java
-
import java.util.HashMap; import java.util.Map; public class Word_Pattern { public class Solution { public boolean wordPattern(String pattern, String str) { if (pattern == null || pattern.length() == 0 || str == null || str.length() == 0) { return false; } String[] tokens = str.split(" "); if (pattern.length() != tokens.length) { return false; } Map<String, Character> inverseMap = new HashMap<>(); Map<Character, String> map = new HashMap<>(); for (int i = 0; i < pattern.length(); i++) { char c = pattern.charAt(i); String token = tokens[i]; // Check the one-one mapping if (!map.containsKey(c) && !inverseMap.containsKey(token)) { map.put(c, token); inverseMap.put(token, c); } else if (map.containsKey(c) && inverseMap.containsKey(token)) { String tokenToCheck = map.get(c); char charToCheck = inverseMap.get(token); if (!tokenToCheck.equals(token) || c != charToCheck) { return false; } } else { // @note: this is for different length of pattern and str return false; } } return true; } } }
-
// OJ: https://leetcode.com/problems/word-pattern/ // Time: O(M + N) // Space: O(M + N) class Solution { public: bool wordPattern(string pattern, string str) { unordered_map<char, string> m; unordered_map<string, char> r; istringstream ss(str); string word; for (char c : pattern) { if (!(ss >> word)) return false; if ((m.count(c) && m[c] != word) || r.count(word) && r[word] != c) return false; m[c] = word; r[word] = c; } return ss.eof(); } };
-
class Solution(object): def wordPattern(self, pattern, str): """ :type pattern: str :type str: str :rtype: bool """ str = str.split() a = zip(pattern, str) print a return len(pattern) == len(str) and len(set(a)) == len(set(pattern)) == len(set(str))