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 | 书影博客

Labels

LeetCode (1432) GeeksforGeeks (1122) LeetCode - Review (1067) Review (882) Algorithm (668) to-do (609) Classic Algorithm (270) Google Interview (237) Classic Interview (222) Dynamic Programming (220) DP (186) Bit Algorithms (145) POJ (141) Math (137) Tree (132) LeetCode - Phone (129) EPI (122) Cracking Coding Interview (119) DFS (115) Difficult Algorithm (115) Lintcode (115) Different Solutions (110) Smart Algorithm (104) Binary Search (96) BFS (91) HackerRank (90) Binary Tree (86) Hard (79) Two Pointers (78) Stack (76) Company-Facebook (75) BST (72) Graph Algorithm (72) Time Complexity (69) Greedy Algorithm (68) Interval (63) Company - Google (62) Geometry Algorithm (61) Interview Corner (61) LeetCode - Extended (61) Union-Find (60) Trie (58) Advanced Data Structure (56) List (56) Priority Queue (53) Codility (52) ComProGuide (50) LeetCode Hard (50) Matrix (50) Bisection (48) Segment Tree (48) Sliding Window (48) USACO (46) Space Optimization (45) Company-Airbnb (41) Greedy (41) Mathematical Algorithm (41) Tree - Post-Order (41) ACM-ICPC (40) Algorithm Interview (40) Data Structure Design (40) Graph (40) Backtracking (39) Data Structure (39) Jobdu (39) Random (39) Codeforces (38) Knapsack (38) LeetCode - DP (38) Recursive Algorithm (38) String Algorithm (38) TopCoder (38) Sort (37) Introduction to Algorithms (36) Pre-Sort (36) Beauty of Programming (35) Must Known (34) Binary Search Tree (33) Follow Up (33) prismoskills (33) Palindrome (32) Permutation (31) Array (30) Google Code Jam (30) HDU (30) Array O(N) (29) Logic Thinking (29) Monotonic Stack (29) Puzzles (29) Code - Detail (27) Company-Zenefits (27) Microsoft 100 - July (27) Queue (27) Binary Indexed Trees (26) TreeMap (26) to-do-must (26) 1point3acres (25) GeeksQuiz (25) Merge Sort (25) Reverse Thinking (25) hihocoder (25) Company - LinkedIn (24) Hash (24) High Frequency (24) Summary (24) Divide and Conquer (23) Proof (23) Game Theory (22) Topological Sort (22) Lintcode - Review (21) Tree - Modification (21) Algorithm Game (20) CareerCup (20) Company - Twitter (20) DFS + Review (20) DP - Relation (20) Brain Teaser (19) DP - Tree (19) Left and Right Array (19) O(N) (19) Sweep Line (19) UVA (19) DP - Bit Masking (18) LeetCode - Thinking (18) KMP (17) LeetCode - TODO (17) Probabilities (17) Simulation (17) String Search (17) Codercareer (16) Company-Uber (16) Iterator (16) Number (16) O(1) Space (16) Shortest Path (16) itint5 (16) DFS+Cache (15) Dijkstra (15) Euclidean GCD (15) Heap (15) LeetCode - Hard (15) Majority (15) Number Theory (15) Rolling Hash (15) Tree Traversal (15) Brute Force (14) Bucket Sort (14) DP - Knapsack (14) DP - Probability (14) Difficult (14) Fast Power Algorithm (14) Pattern (14) Prefix Sum (14) TreeSet (14) Algorithm Videos (13) Amazon Interview (13) Basic Algorithm (13) Codechef (13) Combination (13) Computational Geometry (13) DP - Digit (13) LCA (13) LeetCode - DFS (13) Linked List (13) Long Increasing Sequence(LIS) (13) Math-Divisible (13) Reservoir Sampling (13) mitbbs (13) Algorithm - How To (12) Company - Microsoft (12) DP - Interval (12) DP - Multiple Relation (12) DP - Relation Optimization (12) LeetCode - Classic (12) Level Order Traversal (12) Prime (12) Pruning (12) Reconstruct Tree (12) Thinking (12) X Sum (12) AOJ (11) Bit Mask (11) Company-Snapchat (11) DP - Space Optimization (11) Dequeue (11) Graph DFS (11) MinMax (11) Miscs (11) Princeton (11) Quick Sort (11) Stack - Tree (11) 尺取法 (11) 挑战程序设计竞赛 (11) Coin Change (10) DFS+Backtracking (10) Facebook Hacker Cup (10) Fast Slow Pointers (10) HackerRank Easy (10) Interval Tree (10) Limited Range (10) Matrix - Traverse (10) Monotone Queue (10) SPOJ (10) Starting Point (10) States (10) Stock (10) Theory (10) Tutorialhorizon (10) Kadane - Extended (9) Mathblog (9) Max-Min Flow (9) Maze (9) Median (9) O(32N) (9) Quick Select (9) Stack Overflow (9) System Design (9) Tree - Conversion (9) Use XOR (9) Book Notes (8) Company-Amazon (8) DFS+BFS (8) DP - States (8) Expression (8) Longest Common Subsequence(LCS) (8) One Pass (8) Quadtrees (8) Traversal Once (8) Trie - Suffix (8) 穷竭搜索 (8) Algorithm Problem List (7) All Sub (7) Catalan Number (7) Cycle (7) DP - Cases (7) Facebook Interview (7) Fibonacci Numbers (7) Flood fill (7) Game Nim (7) Graph BFS (7) HackerRank Difficult (7) Hackerearth (7) Inversion (7) Kadane’s Algorithm (7) Manacher (7) Morris Traversal (7) Multiple Data Structures (7) Normalized Key (7) O(XN) (7) Radix Sort (7) Recursion (7) Sampling (7) Suffix Array (7) Tech-Queries (7) Tree - Serialization (7) Tree DP (7) Trie - Bit (7) 蓝桥杯 (7) Algorithm - Brain Teaser (6) BFS - Priority Queue (6) BFS - Unusual (6) Classic Data Structure Impl (6) DP - 2D (6) DP - Monotone Queue (6) DP - Unusual (6) DP-Space Optimization (6) Dutch Flag (6) How To (6) Interviewstreet (6) Knapsack - MultiplePack (6) Local MinMax (6) MST (6) Minimum Spanning Tree (6) Number - Reach (6) Parentheses (6) Pre-Sum (6) Probability (6) Programming Pearls (6) Rabin-Karp (6) Reverse (6) Scan from right (6) Schedule (6) Stream (6) Subset Sum (6) TSP (6) Xpost (6) n00tc0d3r (6) reddit (6) AI (5) Abbreviation (5) Anagram (5) Art Of Programming-July (5) Assumption (5) Bellman Ford (5) Big Data (5) Code - Solid (5) Code Kata (5) Codility-lessons (5) Coding (5) Company - WMware (5) Convex Hull (5) Crazyforcode (5) DFS - Multiple (5) DFS+DP (5) DP - Multi-Dimension (5) DP-Multiple Relation (5) Eulerian Cycle (5) Graph - Unusual (5) Graph Cycle (5) Hash Strategy (5) Immutability (5) Java (5) LogN (5) Manhattan Distance (5) Matrix Chain Multiplication (5) N Queens (5) Pre-Sort: Index (5) Quick Partition (5) Quora (5) Randomized Algorithms (5) Resources (5) Robot (5) SPFA(Shortest Path Faster Algorithm) (5) Shuffle (5) Sieve of Eratosthenes (5) Strongly Connected Components (5) Subarray Sum (5) Sudoku (5) Suffix Tree (5) Swap (5) Threaded (5) Tree - Creation (5) Warshall Floyd (5) Word Search (5) jiuzhang (5)

Popular Posts