update

jason316 · Feb 3, 2015 · d5b052b · d5b052b
1 parent 08be9fd
commit d5b052b
Show file tree

Hide file tree

Showing 2 changed files with 39 additions and 2 deletions.
diff --git a/Python/reverse-words-in-a-string-ii.py b/Python/reverse-words-in-a-string-ii.py
@@ -0,0 +1,34 @@
+# Time: O(n)
+# Space:O(1)
+#
+# Given an input string, reverse the string word by word. A word is defined as a sequence of non-space characters.
+# 
+# The input string does not contain leading or trailing spaces and the words are always separated by a single space.
+# 
+# For example,
+# Given s = "the sky is blue",
+# return "blue is sky the".
+# 
+# Could you do it in-place without allocating extra space?
+#
+
+class Solution:
+    # @param s, a list of 1 length strings, e.g., s = ['h','e','l','l','o']
+    # @return nothing
+    def reverseWords(self, s):
+        self.reverse(s, 0, len(s))
+
+        i = 0
+        for j in xrange(len(s) + 1):
+            if j == len(s) or s[j] == ' ':
+                self.reverse(s, i, j)
+                i = j + 1
+
+    def reverse(self, s, begin, end):
+        for i in xrange((end - begin) / 2):
+            s[begin + i], s[end - 1 - i] = s[end - 1 - i], s[begin + i]
+
+if __name__ == '__main__':
+    s = ['h','e','l','l','o', ' ', 'w', 'o', 'r', 'l', 'd']
+    Solution().reverseWords(s)
+    print s
diff --git a/README.md b/README.md
@@ -1,9 +1,9 @@
 LeetCode
 ======== 
 
-Up to date (2015-01-24), there are total `185` problems on [LeetCode Online Judge](https://oj.leetcode.com/).
+Up to date (2015-02-03), there are total `186` problems on [LeetCode Online Judge](https://oj.leetcode.com/).
 The number of problems is increasing recently.
-Here is the classification of all `185` problems.
+Here is the classification of all `186` problems.
 I'll keep updating for full summary and better solutions. Stay tuned for updates.
 
 --- 
@@ -136,6 +136,7 @@ Problem         |  Solution       |  Time           | Space           | Difficul
 [Multiply Strings] | [multiply-strings.py] | _O(m * n)_ | _O(m + n)_  | Medium         |
 [One Edit Distance] | [one-edit-distance.py] | _O(m + n)_ | _O(1)_    | Medium         |
 [Reverse Words in a String] | [reverse-words-in-a-string.py] | _O(n)_ | _O(n)_ | Medium         |
+[Reverse Words in a String II] | [reverse-words-in-a-string-ii.py] | _O(n)_ | _O(1)_ | Medium         |
 [String to Integer (atoi)] | [string-to-integer-atoi.py] | _O(n)_ | _O(1)_ | Easy      |
 [Text Justification] | [text-justification.py] | _O(n)_ | _O(1)_      | Hard           |
 [Valid Palindrome] | [valid-palindrome.py] | _O(n)_  | _O(1)_         | Easy           |
@@ -164,6 +165,8 @@ Problem         |  Solution       |  Time           | Space           | Difficul
 [one-edit-distance.py]:https://github.com/kamyu104/LeetCode/blob/master/Python/one-edit-distance.py
 [Reverse Words in a String]:https://oj.leetcode.com/problems/reverse-words-in-a-string/
 [reverse-words-in-a-string.py]:https://github.com/kamyu104/LeetCode/blob/master/Python/reverse-words-in-a-string.py
+[Reverse Words in a String II]:https://oj.leetcode.com/problems/reverse-words-in-a-string-ii/
+[reverse-words-in-a-string-ii.py]:https://github.com/kamyu104/LeetCode/blob/master/Python/reverse-words-in-a-string-ii.py
 [String to Integer (atoi)]:https://oj.leetcode.com/problems/string-to-integer-atoi/
 [string-to-integer-atoi.py]:https://github.com/kamyu104/LeetCode/blob/master/Python/string-to-integer-atoi.py
 [Text Justification]:https://oj.leetcode.com/problems/text-justification/