LeetCode 290 - Word Pattern

Related: LeetCode 291 Word Pattern II
[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.

Examples:

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.

Notes:
You may assume pattern contains only lowercase letters, and str contains lowercase letters separated by a single space.

https://discuss.leetcode.com/topic/26339/8-lines-simple-java

public boolean wordPattern(String pattern, String str) {
    String[] words = str.split(" ");
    if (words.length != pattern.length())
        return false;
    Map index = new HashMap();
    for (Integer i=0; i<words.length; ++i)
        if (index.put(pattern.charAt(i), i) != index.put(words[i], i))
            return false;
    return true;
}

I go through the pattern letters and words in parallel and compare the indexes where they last appeared.

Edit 1: Originally I compared the first indexes where they appeared, using putIfAbsent instead of put. That was based on mathsam's solution for the old Isomorphic Strings problem. But then czonzhu's answer below made me realize that put works as well and why.

Edit 2: Switched from

    for (int i=0; i<words.length; ++i)
        if (!Objects.equals(index.put(pattern.charAt(i), i),
                            index.put(words[i], i)))
            return false;

to the current version with i being an Integer object, which allows to compare with just != because there's no autoboxing-same-value-to-different-objects-problem anymore. Thanks to lap_218 for somewhat pointing that out in the comments.

使用字典dict分别记录pattern到word的映射以及word到pattern的映射

这道题和题目Isomorphic Strings十分类似
http://segmentfault.com/a/1190000003827151

    public boolean wordPattern(String pattern, String str) {
        Map<Character, String> map = new HashMap<Character, String>();
        Set<String> set = new HashSet<String>();
        String[] pieces = str.split(" ");
        if(pieces.length != pattern.length()) return false;
        int i = 0;
        for(String s : pieces){
            char p = pattern.charAt(i);
            System.out.println(p);
            // 如果该字符产生过映射
            if(map.containsKey(p)){
                // 且映射的字符串和当前字符串不一样
                if(!s.equals(map.get(p))) return false;
            } else {
            // 如果该字符没有产生过映射
                // 如果当前字符串已经被映射过了
                if(set.contains(s)) return false;
                // 否则新加一组映射
                map.put(p, s);
                set.add(s);
            }
            i++;
        }
        return true;
    }

def wordPattern(self, pattern, str): words = str.split() if len(pattern) != len(words): return False ptnDict, wordDict = {}, {} for ptn, word in zip(pattern, words): if ptn not in ptnDict: ptnDict[ptn] = word if word not in wordDict: wordDict[word] = ptn if wordDict[word] != ptn or ptnDict[ptn] != word: return False return True
http://blog.csdn.net/xudli/article/details/48932055

1.     public boolean wordPattern(String pattern, String str) {  
2.         //input check  
3.           
4.         String[] strs = str.split(" ");  
5.         if(pattern.length() != strs.length  ) return false;  
6.           
7.         Map<Character, String> map = new HashMap<>();  
8.         Set<String> unique = new HashSet<>();  
9.           
10.         for(int i=0; i<pattern.length(); i++) {  
11.             char c = pattern.charAt(i);  
12.             if(map.containsKey(c) ) {  
13.                 if(!map.get(c).equals(strs[i])) return false;  
14.             } else {  
15.                 if(unique.contains(strs[i])) return false;  
16.                 map.put(c, strs[i]);  
17.                 unique.add(strs[i]);  
18.             }  
19.         }  
20.         return true;  
21.     }  

X. 2 Hashmaps
http://buttercola.blogspot.com/2015/10/leetcode-word-pattern.html
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; 

    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;

    }

}

http://shibaili.blogspot.com/2015/10/day-132-287-find-duplicate-number.html
2个hashmap 互相对应

    string getWord(string str, int &index) {

        string rt = "";

        for (; index < str.length(); index++) {

            if (isalpha(str[index])) {

                rt += str[index];

            }else break;

        }

        index++;

        return rt;

    }

    bool wordPattern(string pattern, string str) {

        unordered_map<char,string> pToS;

        unordered_map<string,char> sToP;

        int index = 0;

         

        for (int i = 0; i < pattern.length(); i++) {

            if (index == str.length()) return false;

            string word = getWord(str,index);

            if (pToS.find(pattern[i]) == pToS.end()) {

                pToS[pattern[i]] = word;

            }else if (word != pToS[pattern[i]]) return false;

             

            if (sToP.find(word) == sToP.end()) {

                sToP[word] = pattern[i];

            }else if (sToP[word] != pattern[i]) return false;

        }

         

        return index == str.length() + 1;

    }

X.  http://my.oschina.net/Tsybius2014/blog/514983
Not really better.

另一个办法需要利用HashMap中put函数的性质。

put函数的声明如下：

?

1	public V put(K key, V value)

它的功能是将键值对存入map中，如果map中原本就包含要插入的键，将旧值替换为新值。对于该函数的返回值，如果要插入的键在字典中不存在，则返回null，否则返回替换前的值。

    public boolean wordPattern(String pattern, String str) {

         

        if (pattern.isEmpty() || str.isEmpty()) {

            return false;

        }

         

        String[] s = str.split(" ");

        if (s.length != pattern.length()) {

            return false;

        }

         

        @SuppressWarnings("rawtypes")

        HashMap<Comparable, Integer> hashMap = new HashMap<Comparable, Integer>();

        for (int i = 0; i < pattern.length(); i++) {

            if (!Objects.equals(hashMap.put(pattern.charAt(i), i), hashMap.put(s[i], i)))

                return false;

        }

         

        return true;

    }

X.
Not efficient. As hashMap.containsValue is o(n).
http://my.oschina.net/Tsybius2014/blog/514983

    public boolean wordPattern(String pattern, String str) {

         

        if (pattern.isEmpty() || str.isEmpty()) {

            return false;

        }

         

        String[] s = str.split(" ");

        if (s.length != pattern.length()) {

            return false;

        }

         

        HashMap<Character, String> hashMap = new HashMap<Character, String>();

        for (int i = 0; i < pattern.length(); i++) {

            if (hashMap.containsKey(pattern.charAt(i))) {

                if (!hashMap.get(pattern.charAt(i)).equals(s[i])) {

                    return false;

                }

            } else if (hashMap.containsValue(s[i])) {

                return false;

            } else {

                hashMap.put(pattern.charAt(i), s[i]);

            }

        }

         

        return true;

    }

X. Two HashMap
http://www.cnblogs.com/jcliBlogger/p/4857854.html

 3     bool wordPattern(string pattern, string str) {
 4         unordered_map<char, int> p2i;
 5         unordered_map<string, int> w2i;
 6         istringstream in(str);
 7         int i = 0, n = pattern.length();
 8         for (string word; in >> word; i++) {
 9             if (i >= n || p2i[pattern[i]] != w2i[word])
10                 return false;
11             p2i[pattern[i]] = w2i[word] = i + 1;
12         }
13         return i == n;
14     }

X. http://likemyblogger.blogspot.com/2015/10/leetcode-290-word-pattern.html

    bool wordPattern(string pattern, string str) {

        unordered_map<char, string> hash1;

        unordered_map<string, char> hash2;

        int np = pattern.size();

        int l = 0, r, sz = str.size();

        for(int i=0; i<np; ++i){

            if(l>=sz) return false;//number of words < np

            r = l;

            while(r<sz && str[r]!=' ') r++;

            string word = str.substr(l, r-l);

            l = r+1;

            char c = pattern[i];

             

            if(hash1.count(c)==0){

                hash1[c] = word;

            }else if(hash1[c]!=word){

                return false;

            }

             

            if(hash2.count(word)==0){

                hash2[word] = c;

            }else if(hash2[word]!=c){

                return false;

            }           

        }

        return r==sz;

    }

http://yuancrackcode.com/2015/11/27/word-pattern/

Find all strings that match specific pattern in a dictionary - GeeksforGeeks
Given a dictionary of words, find all strings that matches the given pattern where every character in the pattern is uniquely mapped to a character in the dictionary.

dict = ["abb", "abc", "xyz", "xyy"];
pattern = "foo"
Output: [xyy abb]
Explanation: 
xyy and abb have same character at index 1 and 2 like the pattern

The idea is to encode the pattern in such a way that any word from the dictionary that matches the pattern will have same hash as that of the pattern after encoding. We iterate through all words in dictionary one by one and print the words that have same hash as that of the pattern.

// Function to encode given string

string encodeString(string str)

{

    unordered_map<char, int> map;

    string res = "";

    int i = 0;

    // for each character in given string

    for (char ch : str)

    {

        // If the character is occurring for the first

        // time, assign next unique number to that char

        if (map.find(ch) == map.end())

            map[ch] = i++;

        // append the number associated with current

        // character into the output string

        res += to_string(map[ch]);

    }

    return res;

}

// Function to print all the strings that match the

// given pattern where every character in the pattern is

// uniquely mapped to a character in the dictionary

void findMatchedWords(unordered_set<string> dict,

                      string pattern)

{

    // len is length of the pattern

    int len = pattern.length();

    // encode the string

    string hash = encodeString(pattern);

    // for each word in the dictionary

    for (string word : dict)

    {

        // If size of pattern is same as size of current

        // dictionary word and both pattern and the word

        // has same hash, print the word

        if (word.length() == len && encodeString(word) == hash)

            cout << word << " " ;

    }

}

Read full article from [LeetCode]Word Pattern | 书影博客