Repository: keon/algorithms
Pull request #362 (2018-06-25 06:13:42)

Add some solution 
(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**


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

* **28** of **31**   **(90.32%)**  changed or added relevant lines in **4** files are covered.
* **14** unchanged lines in **2** files lost coverage.
* Overall coverage decreased (**-0.2%**) to **71.172%**

---

|  Changes Missing Coverage | Covered Lines | Changed/Added Lines | % |
| :-----|--------------|--------|---: |
| [algorithms/unix/path/simplify_path.py](https://coveralls.io/builds/17668558/source?filename=algorithms%2Funix%2Fpath%2Fsimplify_path.py#L26) | 10 | 11 | 90.91%
| [algorithms/strings/repeat_string.py](https://coveralls.io/builds/17668558/source?filename=algorithms%2Fstrings%2Frepeat_string.py#L20) | 9 | 11 | 81.82%
<!-- | **Total:** | **28** | **31** | **90.32%** | -->

|  Files with Coverage Reduction | New Missed Lines | % |
| :-----|--------------|--: |
| [tests/test_strings.py](https://coveralls.io/builds/17668558/source?filename=tests%2Ftest_strings.py#L421) | 3 | 97.58% |
| [algorithms/strings/count_binary_substring.py](https://coveralls.io/builds/17668558/source?filename=algorithms%2Fstrings%2Fcount_binary_substring.py#L22) | 11 | 8.33% |
<!-- | **Total:** | **14** |  | -->

|  Totals | [![Coverage Status](https://coveralls.io/builds/17668558/badge)](https://coveralls.io/builds/17668558) |
| :-- | --: |
| Change from base [Build 651](https://coveralls.io/builds/17624178): |  -0.2% |
| Covered Lines: | 3718 |
| Relevant Lines: | 5224 |

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


Patch:
diff --git a/README.md b/README.md
index 8228698..abc9f55 100644
--- 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
index afeb60c..4040c9e 100644
--- a/algorithms/strings/__init__.py
+++ b/algorithms/strings/__init__.py
@@ -27,3 +27,4 @@ from .strong_password import *
 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
new file mode 100644
index 0000000..cc871f6
--- /dev/null
+++ 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
index 68b785c..0d1808d 100644
--- 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
new file mode 100644
index 0000000..8880fc0
--- /dev/null
+++ 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)


Test patch:
diff --git a/tests/test_strings.py b/tests/test_strings.py
index 05d977b..c8b9182 100644
--- a/tests/test_strings.py
+++ b/tests/test_strings.py
@@ -29,7 +29,8 @@ from algorithms.strings import (
     strong_password,
     caesar_cipher,
     contain_string,
-    count_binary_substring
+    count_binary_substring,
+    repeat_string
 )
 
 import unittest
@@ -421,5 +422,10 @@ class TestCountBinarySubstring(unittest.TestCase):
         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
index a243889..e7a6c63 100644
--- 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 @@ class TestUnixPath(unittest.TestCase):
         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/"))