Repository: keon/algorithms
Pull request #389 (2018-08-10 06:51:48)

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


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

* **0** of **1**   **(0.0%)**  changed or added relevant line in **1** file are covered.
* No unchanged relevant lines lost coverage.
* Overall coverage remained the same at **72.316%**

---

|  Changes Missing Coverage | Covered Lines | Changed/Added Lines | % |
| :-----|--------------|--------|---: |
| [algorithms/graph/find_path.py](https://coveralls.io/builds/18420700/source?filename=algorithms%2Fgraph%2Ffind_path.py#L46) | 0 | 1 | 0.0%
<!-- | **Total:** | **0** | **1** | **0.0%** | -->


|  Totals | [![Coverage Status](https://coveralls.io/builds/18420700/badge)](https://coveralls.io/builds/18420700) |
| :-- | --: |
| Change from base [Build 714](https://coveralls.io/builds/18336219): |  0.0% |
| Covered Lines: | 4237 |
| Relevant Lines: | 5859 |

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


Patch:
diff --git a/CONTRIBUTING.md b/CONTRIBUTING.md
index 380bd3d..3ccd4eb 100644
--- a/CONTRIBUTING.md
+++ b/CONTRIBUTING.md
@@ -13,6 +13,7 @@ agree to abide by the [Code of Conduct](CODE_OF_CONDUCT.md).
   * add_XXX if you will add new algorithms or data structures.  
   * fix_XXX if you will fixe a bug on a certain algorithm or data structure.  
   * test_XXX if you wrote a test/s.  
+  * doc_XXX if you added to or edited documentation.
 
 You may contribute by:
 - implementing new algorithms in the repo. Be sure to keep it under
@@ -23,6 +24,7 @@ it doesn't fall under any section. Make sure that your implementation works.
 - finding and fixing bugs.
 - adding examples to explain the algorithms better.
 - adding test cases.
+- improving documentation.
 
 ## Pull Requests
 Push to your fork and [submit a pull request][pr].
diff --git a/README.md b/README.md
index 7bb2689..4d4cbb3 100644
--- a/README.md
+++ b/README.md
@@ -1,4 +1,4 @@
-  <p align="center"><img src="https://raw.githubusercontent.com/keon/algorithms/master/docs/source/_static/logo/logotype1blue.png"></p>
+<p align="center"><img src="https://raw.githubusercontent.com/keon/algorithms/master/docs/source/_static/logo/logotype1blue.png"></p>
 
 English | [简体中文](README_CN.md) | [Deutsch](README_GE.md) | [日本語](README_JP.md) | [한국어](README_KR.md) | [Português](README_PTBR.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/graph/find_path.py b/algorithms/graph/find_path.py
index 5008da0..d1716c0 100644
--- a/algorithms/graph/find_path.py
+++ b/algorithms/graph/find_path.py
@@ -43,7 +43,7 @@ def find_shortest_path(graph, start, end, path=[]):
     shortest = None
     for node in graph[start]:
         if node not in path:
-            newpath = find_shortest_path(graph, start, end, path)
+            newpath = find_shortest_path(graph, node, end, path)
             if newpath:
                 if not shortest or len(newpath) < len(shortest):
                     shortest = newpath
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"]))