Thursday, October 8, 2015

Leetcode: 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.
  1. pattern = "abba", str = "dog cat cat dog" should return true.
  2. pattern = "abba", str = "dog cat cat fish" should return false.
  3. pattern = "aaaa", str = "dog cat cat dog" should return false.
  4. pattern = "abba", str = "dog dog dog dog" should return false.
  1. patterncontains only lowercase alphabetical letters, and str contains words separated by a single space. Each word in str contains only lowercase alphabetical letters.
  2. Both pattern and str do not have leading or trailing spaces.
  3. Each letter in pattern must map to a word with length that is at least 1.
Understand the problem:
The problem can be solved by using hash map. Note that some edge cases must be considered:
1. It must be a one-one mapping. e.g. 
"abba", "dog dog dog dog" => false, since a and b maps to the dog.
"aaaa", "dog cat cat dog" => false, since a maps to both dog and cat. 

So we may use two hash tables to maintain such a one-one mapping relationship. Note that in Java we may use map.containsValue(). 

2. The length of the pattern and number of tokens in the str must be the same. Otherwise, return false; 

Code (Java):
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();
        int i = 0;
        for (i = 0; i < pattern.length(); i++) {
            char digit = pattern.charAt(i);
            String token = tokens[i];
            // Check the one-one mapping
            if (!map.containsKey(digit) && !inverseMap.containsKey(token)) {
                map.put(digit, token);
                inverseMap.put(token, digit);
            } else if (map.containsKey(digit) && inverseMap.containsKey(token)) {
                String token1 = map.get(digit);
                char digit1 = inverseMap.get(token);
                if (!token1.equals(token) || digit != digit1) {
                    return false;
            } else {
                return false;
        return true;

No comments:

Post a Comment