Repository: keon/algorithms
Pull request #486 (2019-03-07 05:29:57)

 fix bugs, add descriptions, and add tests
1. Fixed some bugs in "longest_non_repeat.py"
2. Added description for the algorithm in "anagram.py"
3. Updated description for the algorithm in "generate_abbreviations.py", "letter_combination.py"
4. Added tests for the algorithm in "test_array.py", "test_backtrack.py"

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

* **70** of **73**   **(95.89%)**  changed or added relevant lines in **3** files are covered.
* **2** unchanged lines in **1** file lost coverage.
* Overall coverage increased (+**1.2%**) to **66.206%**

---

|  Changes Missing Coverage | Covered Lines | Changed/Added Lines | % |
| :-----|--------------|--------|---: |
| [algorithms/arrays/longest_non_repeat.py](https://coveralls.io/builds/22036447/source?filename=algorithms%2Farrays%2Flongest_non_repeat.py#L20) | 12 | 15 | 80.0%
<!-- | **Total:** | **70** | **73** | **95.89%** | -->

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

|  Totals | [![Coverage Status](https://coveralls.io/builds/22036447/badge)](https://coveralls.io/builds/22036447) |
| :-- | --: |
| Change from base [Build 870](https://coveralls.io/builds/22035221): |  1.2% |
| Covered Lines: | 4643 |
| Relevant Lines: | 7013 |

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

keon: awesome man

Patch:
diff --git a/algorithms/arrays/longest_non_repeat.py b/algorithms/arrays/longest_non_repeat.py
index c3ba815..786c03d 100644
--- a/algorithms/arrays/longest_non_repeat.py
+++ b/algorithms/arrays/longest_non_repeat.py
@@ -16,6 +16,8 @@ def longest_non_repeat_v1(string):
     Find the length of the longest substring
     without repeating characters.
     """
+    if string is None:
+        return 0
     dict = {}
     max_length = 0
     j = 0
@@ -52,18 +54,19 @@ def get_longest_non_repeat_v1(string):
     Return max_len and the substring as a tuple
     """
     if string is None:
-        return 0
+        return 0, ''
     sub_string = ''
-    temp = []
-    max_len = 0
-    for i in string:
-        if i in temp:
-            temp = []
-        temp.append(i)
-        if len(temp) > max_len:
-            max_len = len(temp)
-            sub_string = ''.join(temp)
-    return max_len, sub_string
+    dict = {}
+    max_length = 0
+    j = 0
+    for i in range(len(string)):
+        if string[i] in dict:
+            j = max(dict[string[i]], j)
+        dict[string[i]] = i + 1
+        if i - j + 1 > max_length:
+            max_length = i - j + 1
+            sub_string = string[j: i + 1]
+    return max_length, sub_string
 
 def get_longest_non_repeat_v2(string):
     """
@@ -73,7 +76,7 @@ def get_longest_non_repeat_v2(string):
     Return max_len and the substring as a tuple
     """
     if string is None:
-        return 0
+        return 0, ''
     sub_string = ''
     start, max_len = 0, 0
     used_char = {}
diff --git a/algorithms/backtrack/anagram.py b/algorithms/backtrack/anagram.py
index 7c807cd..df3f4ab 100644
--- a/algorithms/backtrack/anagram.py
+++ b/algorithms/backtrack/anagram.py
@@ -1,3 +1,12 @@
+"""
+Given two strings, determine if they are equal after reordering.
+
+Examples:
+"apple", "pleap"  -> True
+"apple", "cherry" -> False
+"""
+
+
 def anagram(s1, s2):
     c1 = [0] * 26
     c2 = [0] * 26
diff --git a/algorithms/backtrack/generate_abbreviations.py b/algorithms/backtrack/generate_abbreviations.py
index 1329656..674df93 100644
--- a/algorithms/backtrack/generate_abbreviations.py
+++ b/algorithms/backtrack/generate_abbreviations.py
@@ -1,7 +1,7 @@
 """
 given input word, return the list of abbreviations.
 ex)
-word => [1ord, w1rd, wo1d, w2d, 3d, w3 ... etc]
+word => ['word', 'wor1', 'wo1d', 'wo2', 'w1rd', 'w1r1', 'w2d', 'w3', '1ord', '1or1', '1o1d', '1o2', '2rd', '2r1', '3d', '4']
 """
 
 
diff --git a/algorithms/backtrack/letter_combination.py b/algorithms/backtrack/letter_combination.py
index 8a2f8d1..09f8af8 100644
--- a/algorithms/backtrack/letter_combination.py
+++ b/algorithms/backtrack/letter_combination.py
@@ -2,6 +2,16 @@
 Given a digit string, return all possible letter
 combinations that the number could represent.
 
+A mapping of digit to letters (just like on the telephone buttons) is given below:
+2: "abc"
+3: "def"
+4: "ghi"
+5: "jkl"
+6: "mno"
+7: "pqrs"
+8: "tuv"
+9: "wxyz"
+
 Input:Digit string "23"
 Output: ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].
 """


Test patch:
diff --git a/tests/test_array.py b/tests/test_array.py
index 3fd6e08..c02b275 100644
--- a/tests/test_array.py
+++ b/tests/test_array.py
@@ -3,7 +3,7 @@ from algorithms.arrays import (
     flatten_iter, flatten,
     garage,
     josephus,
-    longest_non_repeat_v1, longest_non_repeat_v2,
+    longest_non_repeat_v1, longest_non_repeat_v2, get_longest_non_repeat_v1, get_longest_non_repeat_v2,
     Interval, merge_intervals,
     missing_ranges,
     move_zeros,
@@ -169,6 +169,40 @@ class TestLongestNonRepeat(unittest.TestCase):
 
         string = "asjrgapa"
         self.assertEqual(longest_non_repeat_v2(string), 6)
+    
+    def test_get_longest_non_repeat_v1(self):
+        
+        string = "abcabcbb"
+        self.assertEqual(get_longest_non_repeat_v1(string), (3, 'abc'))
+
+        string = "bbbbb"
+        self.assertEqual(get_longest_non_repeat_v1(string), (1, 'b'))
+
+        string = "pwwkew"
+        self.assertEqual(get_longest_non_repeat_v1(string), (3, 'wke'))
+
+        string = "dvdf"
+        self.assertEqual(get_longest_non_repeat_v1(string), (3, 'vdf'))
+
+        string = "asjrgapa"
+        self.assertEqual(get_longest_non_repeat_v1(string), (6, 'sjrgap'))
+
+    def test_get_longest_non_repeat_v2(self):
+        
+        string = "abcabcbb"
+        self.assertEqual(get_longest_non_repeat_v2(string), (3, 'abc'))
+
+        string = "bbbbb"
+        self.assertEqual(get_longest_non_repeat_v2(string), (1, 'b'))
+
+        string = "pwwkew"
+        self.assertEqual(get_longest_non_repeat_v2(string), (3, 'wke'))
+
+        string = "dvdf"
+        self.assertEqual(get_longest_non_repeat_v2(string), (3, 'vdf'))
+
+        string = "asjrgapa"
+        self.assertEqual(get_longest_non_repeat_v2(string), (6, 'sjrgap'))
 
 
 class TestMaxOnesIndex(unittest.TestCase):
@@ -314,7 +348,7 @@ class TestThreeSum(unittest.TestCase):
                             {(-4, 1, 3), (-2, -1, 3), (-1, -1, 2)})
 
 
-class TestSuite(unittest.TestCase):
+class TestTwoSum(unittest.TestCase):
 
     def test_two_sum(self):
 
diff --git a/tests/test_backtrack.py b/tests/test_backtrack.py
index c53f9f1..cb0838a 100644
--- a/tests/test_backtrack.py
+++ b/tests/test_backtrack.py
@@ -6,12 +6,17 @@ from algorithms.backtrack import (
     array_sum_combinations,
     unique_array_sum_combinations,
     combination_sum,
+    get_factors,
+    recursive_get_factors,
     find_words,
+    generate_abbreviations,
+    generate_parenthesis_v1,
+    generate_parenthesis_v2,
+    letter_combinations,
     pattern_match,
 )
 
 import unittest
-from algorithms.backtrack.generate_parenthesis import *
 
 
 class TestAddOperator(unittest.TestCase):
@@ -110,6 +115,53 @@ class TestCombinationSum(unittest.TestCase):
         self.assertEqual(combination_sum(candidates2, target2), answer2)
 
 
+class TestFactorCombinations(unittest.TestCase):
+
+    def test_get_factors(self):
+        target1 = 32
+        answer1 = [
+            [2, 16],
+            [2, 2, 8],
+            [2, 2, 2, 4],
+            [2, 2, 2, 2, 2],
+            [2, 4, 4],
+            [4, 8]
+        ]
+        self.assertEqual(sorted(get_factors(target1)), sorted(answer1))
+        
+        target2 = 12
+        answer2 = [
+            [2, 6],
+            [2, 2, 3],
+            [3, 4]
+        ]
+        self.assertEqual(sorted(get_factors(target2)), sorted(answer2))
+        self.assertEqual(sorted(get_factors(1)), [])
+        self.assertEqual(sorted(get_factors(37)), [])
+    
+    def test_recursive_get_factors(self):
+        target1 = 32
+        answer1 = [
+            [2, 16],
+            [2, 2, 8],
+            [2, 2, 2, 4],
+            [2, 2, 2, 2, 2],
+            [2, 4, 4],
+            [4, 8]
+        ]
+        self.assertEqual(sorted(recursive_get_factors(target1)), sorted(answer1))
+        
+        target2 = 12
+        answer2 = [
+            [2, 6],
+            [2, 2, 3],
+            [3, 4]
+        ]
+        self.assertEqual(sorted(recursive_get_factors(target2)), sorted(answer2))
+        self.assertEqual(sorted(recursive_get_factors(1)), [])
+        self.assertEqual(sorted(recursive_get_factors(37)), [])
+
+
 class TestFindWords(unittest.TestCase):
 
     def test_normal(self):
@@ -158,6 +210,21 @@ class TestFindWords(unittest.TestCase):
         self.assertTrue(len(find_words(board, words)) == 5)
 
 
+class TestGenerateAbbreviations(unittest.TestCase):
+    def test_generate_abbreviations(self):
+        word1 = "word"
+        answer1 = ['word', 'wor1', 'wo1d', 'wo2', 'w1rd', 'w1r1', 'w2d', 'w3',
+            '1ord', '1or1', '1o1d', '1o2', '2rd', '2r1', '3d', '4']
+        self.assertEqual(sorted(generate_abbreviations(word1)), sorted(answer1))
+
+        word2 = "hello"
+        answer2 = ['hello', 'hell1', 'hel1o', 'hel2', 'he1lo', 'he1l1', 'he2o',
+            'he3', 'h1llo', 'h1ll1', 'h1l1o', 'h1l2', 'h2lo', 'h2l1', 'h3o', 'h4',
+            '1ello', '1ell1', '1el1o', '1el2', '1e1lo', '1e1l1', '1e2o', '1e3',
+            '2llo', '2ll1', '2l1o', '2l2', '3lo', '3l1', '4o', '5']
+        self.assertEqual(sorted(generate_abbreviations(word2)), sorted(answer2))
+
+
 class TestPatternMatch(unittest.TestCase):
 
     def test_pattern_match(self):
@@ -172,6 +239,7 @@ class TestPatternMatch(unittest.TestCase):
         self.assertTrue(pattern_match(pattern2, string2))
         self.assertFalse(pattern_match(pattern3, string3))
 
+
 class TestGenerateParenthesis(unittest.TestCase):
 
     def test_generate_parenthesis(self):
@@ -180,7 +248,19 @@ class TestGenerateParenthesis(unittest.TestCase):
         self.assertEqual(generate_parenthesis_v2(2), ['(())', '()()'])
         self.assertEqual(generate_parenthesis_v2(3), ['((()))', '(()())', '(())()', '()(())', '()()()'])
 
+
+class TestLetterCombinations(unittest.TestCase):
+
+    def test_letter_combinations(self):
+        digit1 = "23"
+        answer1 = ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"]
+        self.assertEqual(sorted(letter_combinations(digit1)), sorted(answer1))
+
+        digit2 = "34"
+        answer2 = ['dg', 'dh', 'di', 'eg', 'eh', 'ei', 'fg', 'fh', 'fi']
+        self.assertEqual(sorted(letter_combinations(digit2)), sorted(answer2))
+
+
 if __name__ == '__main__':
 
     unittest.main()
-