Repository: keon/algorithms
Pull request #387 (2018-08-05 20:41:45)

PR to add some hash problems
(Put an `X` inside the `[ ]` to denote check mark `[X]`.)


- [x] **If creating a new file :**
  - [x] added links to it in the README files ?
  - [x] included tests with it ?
  - [x] added description (overview of algorithm, time and space compleixty, and possible edge case) in docstrings ?

- [ ] **if done some changes :**
  - [ ] wrote short description in the PR explaining what the changes do ?
  - [ ] Fixes #[issue number] if related to any issue

- [ ] **other**


danghai: @goswami-rahul @keon I have updated!

coveralls: ## Pull Request Test Coverage Report for [Build 715](https://coveralls.io/builds/18393837)

* **62** of **65**   **(95.38%)**  changed or added relevant lines in **6** files are covered.
* **5** unchanged lines in **2** files lost coverage.
* Overall coverage decreased (**-0.6%**) to **71.426%**

---

|  Changes Missing Coverage | Covered Lines | Changed/Added Lines | % |
| :-----|--------------|--------|---: |
| [algorithms/map/word_pattern.py](https://coveralls.io/builds/18393837/source?filename=algorithms%2Fmap%2Fword_pattern.py#L30) | 14 | 15 | 93.33%
| [algorithms/map/is_isomorphic.py](https://coveralls.io/builds/18393837/source?filename=algorithms%2Fmap%2Fis_isomorphic.py#L28) | 12 | 14 | 85.71%
<!-- | **Total:** | **62** | **65** | **95.38%** | -->

|  Files with Coverage Reduction | New Missed Lines | % |
| :-----|--------------|--: |
| [algorithms/sort/top_sort.py](https://coveralls.io/builds/18393837/source?filename=algorithms%2Fsort%2Ftop_sort.py#L41) | 2 | 90.38% |
| [tests/test_backtrack.py](https://coveralls.io/builds/18393837/source?filename=tests%2Ftest_backtrack.py#L90) | 3 | 95.92% |
<!-- | **Total:** | **5** |  | -->

|  Totals | [![Coverage Status](https://coveralls.io/builds/18393837/badge)](https://coveralls.io/builds/18393837) |
| :-- | --: |
| Change from base [Build 712](https://coveralls.io/builds/18292597): |  -0.6% |
| Covered Lines: | 4297 |
| Relevant Lines: | 6016 |

---
##### 💛  - [Coveralls](https://coveralls.io)


Patch:
diff --git a/README.md b/README.md
index 7bb2689..9341001 100644
--- 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
index a663c8a..233348d 100644
--- 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
new file mode 100644
index 0000000..066d8c2
--- /dev/null
+++ 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
new file mode 100644
index 0000000..62342e5
--- /dev/null
+++ 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
new file mode 100644
index 0000000..bee2f7a
--- /dev/null
+++ 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
new file mode 100644
index 0000000..534e5de
--- /dev/null
+++ b/algorithms/set/__init__.py
@@ -0,0 +1,1 @@
+from .find_keyboard_row import *
diff --git a/algorithms/set/find_keyboard_row.py b/algorithms/set/find_keyboard_row.py
new file mode 100644
index 0000000..e00e368
--- /dev/null
+++ 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


Test patch:
diff --git a/tests/test_map.py b/tests/test_map.py
index 5786803..aaff34a 100644
--- 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 @@ class TestSeparateChainingHashTable(unittest.TestCase):
         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
new file mode 100644
index 0000000..37aea6f
--- /dev/null
+++ 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"]))