[LeetCode] Word Pattern

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.

Examples: pattern = "abba", str = "dog cat cat dog" should return true. pattern = "abba", str = "dog cat cat fish" should return false. pattern = "aaaa", str = "dog cat cat dog" should return false. pattern = "abba", str = "dog dog dog dog" should return false.

HashMap

Time Complexity
O(n)
Space Complexity
O(n)

思路

Build a hashmap, split the str into array of string. Use string in str as key, character in pattern as value.
Iterate the hashmap, there are three situations:
First, the key is not in hashmap, create the key value pair.
Second, the key is not in hashmap, check if the value is already in hashmap and match the pattern.
Third, the key is already in hashmap, check if the value match, if not return false.

代码

public boolean wordPattern(String pattern, String str) {
    //corner case
    if(pattern == null || pattern.length() == 0 || str == null || str.length() == 0) return false;
    
    //key: string in str; value: character in pattern
    Map<String, Character> map = new HashMap<String, Character>();
    
    String[] s = str.split(" ");
    
    if(pattern.length() != s.length) return false;
    
    char[] chars = pattern.toCharArray();
    
    for(int i = 0; i < s.length; i++){
        //if key in hashmap doesn't have string yet, check if the character in pattern is already in hashmap as value
        //if it is, return fasle, if it doesn't, put the character in hashmap
        if(!map.containsKey(s[i])){
            if(map.containsValue(pattern.charAt(i))) return false;
            map.put(s[i], chars[i]);
        }else{
            //if the map already contians the string, and the value of character doesn't match, return false
            if(map.get(s[i]) != chars[i]) return false;
        }
    }
    return true;
}

评论

暂无评论