PR to add some hash problems (keon#387)

Hai Hoang Dang · goswami-rahul · commit b02e3bfe362a · 2018-08-14T17:22:25.000+05:30
* Add word_pattern in hash map

* Add ismorphic to hash table

* Add is_anagram to hash table

* Add find_keyboard_row to set

* Fix the issue
diff --git a/README.md b/README.md
@@ -179,6 +179,9 @@ If you want to uninstall algorithms, it is as simple as:
     - [longest_common_subsequence](algorithms/map/longest_common_subsequence.py)
     - [randomized_set](algorithms/map/randomized_set.py)
     - [valid_sudoku](algorithms/map/valid_sudoku.py)
+    - [word_pattern](algorithms/map/word_pattern.py)
+    - [is_isomorphic](algorithms/map/is_isomorphic.py)
+    - [is_anagram](algorithms/map/is_anagram.py)    
 - [maths](algorithms/maths)
     - [base_conversion](algorithms/maths/base_conversion.py)
     - [combination](algorithms/maths/combination.py)
@@ -231,6 +234,7 @@ If you want to uninstall algorithms, it is as simple as:
 - [set](algorithms/set)
     - [randomized_set](algorithms/set/randomized_set.py)
     - [set_covering](algorithms/set/set_covering.py)
+    - [find_keyboard_row](algorithms/set/find_keyboard_row.py)
 - [sort](algorithms/sort)
     - [bitonic_sort](algorithms/sort/bitonic_sort.py)
     - [bogo_sort](algorithms/sort/bogo_sort.py)
diff --git a/algorithms/map/__init__.py b/algorithms/map/__init__.py
@@ -1,2 +1,5 @@
 from .hashtable import *
 from .separate_chaining_hashtable import *
+from .word_pattern import *
+from .is_isomorphic import *
+from .is_anagram import *
diff --git a/algorithms/map/is_anagram.py b/algorithms/map/is_anagram.py
@@ -0,0 +1,29 @@
+"""
+Given two strings s and t , write a function to determine if t is an anagram of s.
+
+Example 1:
+Input: s = "anagram", t = "nagaram"
+Output: true
+
+Example 2:
+Input: s = "rat", t = "car"
+Output: false
+
+Note:
+You may assume the string contains only lowercase alphabets.
+
+Reference: https://leetcode.com/problems/valid-anagram/description/
+"""
+def is_anagram(s, t):
+    """
+    :type s: str
+    :type t: str
+    :rtype: bool
+    """
+    maps = {}
+    mapt = {}
+    for i in s:
+        maps[i] = maps.get(i, 0) + 1
+    for i in t:
+        mapt[i] = mapt.get(i, 0) + 1
+    return maps == mapt
diff --git a/algorithms/map/is_isomorphic.py b/algorithms/map/is_isomorphic.py
@@ -0,0 +1,40 @@
+"""
+Given two strings s and t, determine if they are isomorphic.
+Two strings are isomorphic if the characters in s can be replaced to get t.
+All occurrences of a character must be replaced with another character while
+preserving the order of characters. No two characters may map to the same
+character but a character may map to itself.
+
+Example 1:
+Input: s = "egg", t = "add"
+Output: true
+
+Example 2:
+Input: s = "foo", t = "bar"
+Output: false
+
+Example 3:
+Input: s = "paper", t = "title"
+Output: true
+Reference: https://leetcode.com/problems/isomorphic-strings/description/
+"""
+def is_isomorphic(s, t):
+    """
+    :type s: str
+    :type t: str
+    :rtype: bool
+    """
+    if len(s) != len(t):
+        return False
+    dict = {}
+    set_value = set()
+    for i in range(len(s)):
+        if s[i] not in dict:
+            if t[i] in set_value:
+                return False
+            dict[s[i]] = t[i]
+            set_value.add(t[i])
+        else:
+            if dict[s[i]] != t[i]:
+                return False
+    return True
diff --git a/algorithms/map/word_pattern.py b/algorithms/map/word_pattern.py
@@ -0,0 +1,40 @@
+"""
+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 separated by a single space.
+Reference: https://leetcode.com/problems/word-pattern/description/
+"""
+def word_pattern(pattern, str):
+    dict = {}
+    set_value = set()
+    list_str = str.split()
+    if len(list_str) != len(pattern):
+        return False
+    for i in range(len(pattern)):
+        if pattern[i] not in dict:
+            if list_str[i] in set_value:
+                return False
+            dict[pattern[i]] = list_str[i]
+            set_value.add(list_str[i])
+        else:
+            if dict[pattern[i]] != list_str[i]:
+                return False
+    return True
diff --git a/algorithms/set/__init__.py b/algorithms/set/__init__.py
@@ -0,0 +1 @@
+from .find_keyboard_row import *
diff --git a/algorithms/set/find_keyboard_row.py b/algorithms/set/find_keyboard_row.py
@@ -0,0 +1,26 @@
+"""
+Given a List of words, return the words that can be typed using letters of
+alphabet on only one row's of American keyboard.
+
+For example:
+Input: ["Hello", "Alaska", "Dad", "Peace"]
+Output: ["Alaska", "Dad"]
+
+Reference: https://leetcode.com/problems/keyboard-row/description/
+"""
+def find_keyboard_row(words):
+    """
+    :type words: List[str]
+    :rtype: List[str]
+    """
+    keyboard = [
+        set('qwertyuiop'),
+        set('asdfghjkl'),
+        set('zxcvbnm'),
+    ]
+    result = []
+    for word in words:
+        for key in keyboard:
+            if set(word.lower()).issubset(key):
+                result.append(word)
+    return result
diff --git a/tests/test_map.py b/tests/test_map.py
@@ -1,6 +1,9 @@
 from algorithms.map import (
     HashTable, ResizableHashTable,
-    Node, SeparateChainingHashTable
+    Node, SeparateChainingHashTable,
+    word_pattern,
+    is_isomorphic,
+    is_anagram
 )
 
 import unittest
@@ -147,6 +150,28 @@ def test_get_none_if_key_missing_and_hash_collision(self):
         self.assertEqual(None, m.get(11))
 
 
+class TestWordPattern(unittest.TestCase):
+    def test_word_pattern(self):
+        self.assertTrue(word_pattern("abba", "dog cat cat dog"))
+        self.assertFalse(word_pattern("abba", "dog cat cat fish"))
+        self.assertFalse(word_pattern("abba", "dog dog dog dog"))
+        self.assertFalse(word_pattern("aaaa", "dog cat cat dog"))
+
+
+class TestIsSomorphic(unittest.TestCase):
+    def test_is_isomorphic(self):
+        self.assertTrue(is_isomorphic("egg", "add"))
+        self.assertFalse(is_isomorphic("foo", "bar"))
+        self.assertTrue(is_isomorphic("paper", "title"))
+
+
+class TestIsAnagram(unittest.TestCase):
+    def test_is_anagram(self):
+        self.assertTrue(is_anagram("anagram", "nagaram"))
+        self.assertFalse(is_anagram("rat", "car"))
+
+
+
 
 if __name__ == "__main__":
     unittest.main()
diff --git a/tests/test_set.py b/tests/test_set.py
@@ -0,0 +1,10 @@
+from algorithms.set import (
+    find_keyboard_row
+)
+
+import unittest
+
+class TestFindKeyboardRow(unittest.TestCase):
+    def test_find_keyboard_row(self):
+        self.assertEqual(["Alaska", "Dad"],
+                         find_keyboard_row(["Hello", "Alaska", "Dad", "Peace"]))
