PR to add some problem (keon#378)

Hai Hoang Dang · web-flow · commit 48072b41ace2 · 2018-08-02T07:27:07.000-07:00
* Add longest_common_prefix to string

* Add brute force way for is_rotated, add rotate to string

* Add first_unique_char to string

* Add repeat_substring to string
diff --git a/README.md b/README.md
@@ -295,6 +295,10 @@ If you want to uninstall algorithms, it is as simple as:
     - [count_binary_substring](algorithms/strings/count_binary_substring.py)
     - [repeat_string](algorithms/strings/repeat_string.py)
     - [min_distance](algorithms/strings/min_distance.py)
+    - [longest_common_prefix](algorithms/strings/longest_common_prefix.py)
+    - [rotate](algorithms/strings/rotate.py)
+    - [first_unique_char](algorithms/strings/first_unique_char.py)
+    - [repeat_substring](algorithms/strings/repeat_substring.py)     
 - [tree](algorithms/tree)
     - [bst](algorithms/tree/tree/bst)
         - [array2bst](algorithms/tree/bst/array2bst.py)
diff --git a/algorithms/strings/__init__.py b/algorithms/strings/__init__.py
@@ -30,3 +30,7 @@
 from .repeat_string import *
 from .text_justification import *
 from .min_distance import *
+from .longest_common_prefix import *
+from .rotate import *
+from .first_unique_char import *
+from .repeat_substring import *
diff --git a/algorithms/strings/first_unique_char.py b/algorithms/strings/first_unique_char.py
@@ -0,0 +1,27 @@
+"""
+Given a string, find the first non-repeating character in it and return it's
+index. If it doesn't exist, return -1.
+
+For example:
+s = "leetcode"
+return 0.
+
+s = "loveleetcode",
+return 2.
+
+Reference: https://leetcode.com/problems/first-unique-character-in-a-string/description/
+"""
+def first_unique_char(s):
+    """
+    :type s: str
+    :rtype: int
+    """
+    if (len(s) == 1):
+        return 0
+    ban = []
+    for i in range(len(s)):
+        if all(s[i] != s[k] for k in range(i + 1, len(s))) == True and s[i] not in ban:
+            return i
+        else:
+            ban.append(s[i])
+    return -1   
diff --git a/algorithms/strings/is_rotated.py b/algorithms/strings/is_rotated.py
@@ -6,10 +6,26 @@
 
 accepts two strings
 returns bool
+Reference: https://leetcode.com/problems/rotate-string/description/
 """
 
 def is_rotated(s1, s2):
     if len(s1) == len(s2):
         return s2 in s1 + s1
     else:
-        return False
+        return False
+
+"""
+Another solution: brutal force
+Complexity: O(N^2)
+"""
+def is_rotated_v1(s1, s2):
+    if len(s1) != len(s2):
+        return False
+    if len(s1) == 0:
+        return True
+
+    for c in range(len(s1)):
+        if all(s1[(c + i) % len(s1)] == s2[i] for i in range(len(s1))):
+            return True
+    return False
diff --git a/algorithms/strings/longest_common_prefix.py b/algorithms/strings/longest_common_prefix.py
@@ -0,0 +1,66 @@
+"""
+Write a function to find the longest common prefix string amongst an array of strings.
+
+If there is no common prefix, return an empty string "".
+
+Example 1:
+Input: ["flower","flow","flight"]
+Output: "fl"
+
+Example 2:
+Input: ["dog","racecar","car"]
+Output: ""
+Explanation: There is no common prefix among the input strings.
+
+Reference: https://leetcode.com/problems/longest-common-prefix/description/
+"""
+
+"""
+First solution: Horizontal scanning
+"""
+def common_prefix(s1, s2):
+    "Return prefix common of 2 strings"
+    if not s1 or not s2:
+        return ""
+    k = 0
+    while s1[k] == s2[k]:
+        k = k + 1
+        if k >= len(s1) or k >= len(s2):
+            return s1[0:k]
+    return s1[0:k]
+
+def longest_common_prefix_v1(strs):
+    if not strs:
+        return ""
+    result = strs[0]
+    for i in range(len(strs)):
+        result = common_prefix(result, strs[i])
+    return result
+
+"""
+Second solution: Vertical scanning
+"""
+def longest_common_prefix_v2(strs):
+    if not strs:
+        return ""
+    for i in range(len(strs[0])):
+        for string in strs[1:]:
+            if i == len(string) or string[i] != strs[0][i]:
+                return strs[0][0:i]
+    return strs[0]
+
+"""
+Third solution: Divide and Conquer
+"""
+def longest_common_prefix_v3(strs):
+    if not strs:
+        return ""
+    return longest_common(strs, 0, len(strs) -1)
+
+def longest_common(strs, left, right):
+    if left == right:
+        return strs[left]
+    mid = (left + right) // 2
+    lcp_left = longest_common(strs, left, mid)
+    lcp_right = longest_common(strs, mid + 1, right)
+    return common_prefix(lcp_left, lcp_right)
diff --git a/algorithms/strings/repeat_substring.py b/algorithms/strings/repeat_substring.py
@@ -0,0 +1,25 @@
+"""
+Given a non-empty string check if it can be constructed by taking
+a substring of it and appending multiple copies of the substring together.
+
+For example:
+Input: "abab"
+Output: True
+Explanation: It's the substring "ab" twice.
+
+Input: "aba"
+Output: False
+
+Input: "abcabcabcabc"
+Output: True
+Explanation: It's the substring "abc" four times.
+
+Reference: https://leetcode.com/problems/repeated-substring-pattern/description/
+"""
+def repeat_substring(s):
+    """
+    :type s: str
+    :rtype: bool
+    """
+    str = (s + s)[1:-1]
+    return s in str
diff --git a/algorithms/strings/rotate.py b/algorithms/strings/rotate.py
@@ -0,0 +1,18 @@
+"""
+Given a strings s and int k, return a string that rotates k times
+
+For example,
+rotate("hello", 2) return "llohe"
+rotate("hello", 5) return "hello"
+rotate("hello", 6) return "elloh"
+rotate("hello", 7) return "llohe"
+
+accepts two strings
+returns bool
+"""
+def rotate(s, k):
+    double_s = s + s
+    if k <= len(s):
+        return double_s[k:k + len(s)]
+    else:
+        return double_s[k-len(s):k]
diff --git a/tests/test_strings.py b/tests/test_strings.py
@@ -9,7 +9,7 @@
     int_to_roman,
     is_palindrome, is_palindrome_reverse,
     is_palindrome_two_pointer, is_palindrome_stack,
-    is_rotated,
+    is_rotated, is_rotated_v1,
     license_number,
     make_sentence,
     is_merge_recursive, is_merge_iterative,
@@ -32,7 +32,11 @@
     count_binary_substring,
     repeat_string,
     text_justification,
-    min_distance
+    min_distance,
+    longest_common_prefix_v1, longest_common_prefix_v2, longest_common_prefix_v3,
+    rotate,
+    first_unique_char,
+    repeat_substring
 )
 
 import unittest
@@ -201,6 +205,21 @@ def test_is_rotated(self):
         self.assertFalse(is_rotated("hello", "lloh"))
         self.assertTrue(is_rotated("", ""))
 
+    def test_is_rotated_v1(self):
+        self.assertTrue(is_rotated_v1("hello", "hello"))
+        self.assertTrue(is_rotated_v1("hello", "llohe"))
+        self.assertFalse(is_rotated_v1("hello", "helol"))
+        self.assertFalse(is_rotated_v1("hello", "lloh"))
+        self.assertTrue(is_rotated_v1("", ""))
+
+
+class TestRotated(unittest.TestCase):
+    def test_rotate(self):
+        self.assertEqual("llohe", rotate("hello", 2))
+        self.assertEqual("hello", rotate("hello", 5))
+        self.assertEqual("elloh", rotate("hello", 6))
+        self.assertEqual("llohe", rotate("hello", 7))
+
 
 class TestLicenseNumber(unittest.TestCase):
     """[summary]
@@ -475,6 +494,29 @@ def test_min_distance(self):
         self.assertEqual(2, min_distance("sea", "eat"))
         self.assertEqual(6, min_distance("abAlgocrithmf", "Algorithmmd"))
 
+class TestLongestCommonPrefix(unittest.TestCase):
+    def test_longest_common_prefix(self):
+        # Test first solution
+        self.assertEqual("fl", longest_common_prefix_v1(["flower","flow","flight"]))
+        self.assertEqual("", longest_common_prefix_v1(["dog","racecar","car"]))
+        # Test second solution
+        self.assertEqual("fl", longest_common_prefix_v2(["flower","flow","flight"]))
+        self.assertEqual("", longest_common_prefix_v2(["dog","racecar","car"]))
+        # Test third solution
+        self.assertEqual("fl", longest_common_prefix_v3(["flower","flow","flight"]))
+        self.assertEqual("", longest_common_prefix_v3(["dog","racecar","car"]))
+
+class TestFirstUniqueChar(unittest.TestCase):
+    def test_first_unique_char(self):
+        self.assertEqual(0, first_unique_char("leetcode"))
+        self.assertEqual(2, first_unique_char("loveleetcode"))
+
+class TestRepeatSubstring(unittest.TestCase):
+    def test_repeat_substring(self):
+        self.assertTrue(repeat_substring("abab"))
+        self.assertFalse(repeat_substring("aba"))
+        self.assertTrue(repeat_substring("abcabcabcabc"))
+
 
 if __name__ == "__main__":
     unittest.main()
