Added some solution (keon#362)

Hai Hoang Dang · goswami-rahul · commit 7520795db8a4 · 2018-06-28T00:09:13.000+05:30
* Add simplify path

* Add repeat string
diff --git a/README.md b/README.md
@@ -291,6 +291,7 @@ If you want to uninstall algorithms, it is as simple as:
     - [caesar_cipher](algorithms/strings/caesar_cipher.py)
     - [contain_string](algorithms/strings/contain_string.py)
     - [count_binary_substring](algorithms/strings/count_binary_substring.py)
+    - [repeat_string](algorithms/strings/repeat_string.py)
 - [tree](algorithms/tree)
     - [bst](algorithms/tree/tree/bst)
         - [array2bst](algorithms/tree/bst/array2bst.py)
@@ -343,6 +344,7 @@ If you want to uninstall algorithms, it is as simple as:
         - [join_with_slash](algorithms/unix/path/join_with_slash.py)
         - [full_path](algorithms/unix/path/full_path.py)
         - [split](algorithms/unix/path/split.py)
+        - [simplify_path](algorithms/unix/path/simplify_path.py)
 - [union-find](algorithms/union-find)
     - [count_islands](algorithms/union-find/count_islands.py)
 
diff --git a/algorithms/strings/__init__.py b/algorithms/strings/__init__.py
@@ -27,3 +27,4 @@
 from .caesar_cipher import *
 from .contain_string import *
 from .count_binary_substring import *
+from .repeat_string import *
diff --git a/algorithms/strings/repeat_string.py b/algorithms/strings/repeat_string.py
@@ -0,0 +1,24 @@
+"""
+Given two strings A and B, find the minimum number of times A has to be repeated such that B is a substring of it. If no such solution, return -1.
+
+For example, with A = "abcd" and B = "cdabcdab".
+
+Return 3, because by repeating A three times (“abcdabcdabcd”), B is a substring of it; and B is not a substring of A repeated two times ("abcdabcd").
+
+Note:
+The length of A and B will be between 1 and 10000.
+
+Reference: https://leetcode.com/problems/repeated-string-match/description/
+"""
+def repeat_string(A, B):
+    count = 1
+    tmp = A
+    max_count = (len(B) / len(A)) + 1
+    while not(B in tmp):
+        tmp = tmp + A
+        if (count > max_count):
+            count = -1
+            break
+        count = count + 1
+
+    return count
diff --git a/algorithms/unix/__init__.py b/algorithms/unix/__init__.py
@@ -1,3 +1,4 @@
 from .path.join_with_slash import *
 from .path.full_path import *
 from .path.split import *
+from .path.simplify_path import *
diff --git a/algorithms/unix/path/simplify_path.py b/algorithms/unix/path/simplify_path.py
@@ -0,0 +1,29 @@
+"""
+Given an absolute path for a file (Unix-style), simplify it.
+
+For example,
+path = "/home/", => "/home"
+path = "/a/./b/../../c/", => "/c"
+
+Corner Cases:
+
+Did you consider the case where path = "/../"?
+In this case, you should return "/".
+Another corner case is the path might contain multiple slashes '/' together, such as "/home//foo/".
+In this case, you should ignore redundant slashes and return "/home/foo".
+
+Reference: https://leetcode.com/problems/simplify-path/description/
+"""
+
+import os
+def simplify_path_v1(path):
+    return os.path.abspath(path)
+
+def simplify_path_v2(path):
+    stack, tokens = [], path.split("/")
+    for token in tokens:
+        if token == ".." and stack:
+            stack.pop()
+        elif token != ".." and token != "." and token:
+            stack.append(token)
+    return "/" + "/".join(stack)
diff --git a/tests/test_strings.py b/tests/test_strings.py
@@ -29,7 +29,8 @@
     strong_password,
     caesar_cipher,
     contain_string,
-    count_binary_substring
+    count_binary_substring,
+    repeat_string
 )
 
 import unittest
@@ -421,5 +422,10 @@ def test_count_binary_substring(self):
         self.assertEqual(4, count_binary_substring("10101"))
         self.assertEqual(3, count_binary_substring("00110"))
 
+class TestCountBinarySubstring(unittest.TestCase):
+    def test_repeat_string(self):
+        self.assertEqual(3, repeat_string("abcd","cdabcdab"))
+        self.assertEqual(4, repeat_string("bb", "bbbbbbb"))
+
 if __name__ == "__main__":
     unittest.main()
diff --git a/tests/test_unix.py b/tests/test_unix.py
@@ -1,7 +1,8 @@
 from algorithms.unix import (
     join_with_slash,
     full_path,
-    split
+    split,
+    simplify_path_v1, simplify_path_v2
 )
 import os
 import unittest
@@ -33,3 +34,9 @@ def test_split(self):
         expect_result = split(path)
         self.assertEqual("algorithms/unix", expect_result[0])
         self.assertEqual("test.py", expect_result[1])
+
+    def test_simplify_path(self):
+        self.assertEqual("/", simplify_path_v1("/../"))
+        self.assertEqual("/home/foo", simplify_path_v1("/home//foo/"))
+        self.assertEqual("/", simplify_path_v2("/../"))
+        self.assertEqual("/home/foo", simplify_path_v2("/home//foo/"))
