New Problem "Is Subsequence"

haoel · haoel · commit ea1a2130970c · 2016-09-08T01:42:00.000+08:00
diff --git a/README.md b/README.md
@@ -8,6 +8,7 @@ LeetCode
 
 | # | Title | Solution | Difficulty |
 |---| ----- | -------- | ---------- |
+|392|[Is Subsequence](https://leetcode.com/problems/is-subsequence/) | [C++](./algorithms/cpp/isSubsequence/IsSubsequence.cpp)|Medium|
 |391|[Perfect Rectangle](https://leetcode.com/problems/perfect-rectangle/) | [C++](./algorithms/cpp/perfectRectangle/PerfectRectangle.cpp)|Hard|
 |390|[Elimination Game](https://leetcode.com/contest/2/problems/elimination-game/) | [C++](./algorithms/cpp/eliminationGame/EliminationGame.cpp)|Medium|
 |389|[Find the Difference](https://leetcode.com/problems/find-the-difference/) | [C++](./algorithms/cpp/findTheDifference/FindTheDifference.cpp)|Easy|
diff --git a/algorithms/cpp/isSubsequence/IsSubsequence.cpp b/algorithms/cpp/isSubsequence/IsSubsequence.cpp
@@ -0,0 +1,50 @@
+// Source : https://leetcode.com/problems/is-subsequence/
+// Author : Hao Chen
+// Date   : 2016-09-08
+
+/*************************************************************************************** 
+ *
+ * Given a string s and a string t, check if s is subsequence of t.
+ * 
+ * You may assume that there is only lower case English letters in both s and t. t is 
+ * potentially a very long (length ~= 500,000) string, and s is a short string (
+ * 
+ * A subsequence of a string is a new string which is formed from the original string 
+ * by deleting some (can be none) of the characters without disturbing the relative 
+ * positions of the remaining characters. (ie, "ace" is a subsequence of "abcde" while 
+ * "aec" is not).
+ * 
+ * Example 1:
+ * s = "abc", t = "ahbgdc"
+ * 
+ * Return true.
+ * 
+ * Example 2:
+ * s = "axc", t = "ahbgdc"
+ * 
+ * Return false.
+ * 
+ * Follow up:
+ * If there are lots of incoming S, say S1, S2, ... , Sk where k >= 1B, and you want to 
+ * check one by one to see if T has its subsequence. In this scenario, how would you 
+ * change your code?
+ ***************************************************************************************/
+
+class Solution {
+public:
+    bool isSubsequence(string s, string t) {
+        if (s.size() <= 0) return true;
+        
+        int ps=0, pt=0;
+        while (pt < t.size()) {
+            if (s[ps] == t[pt]) {
+                ps++; pt++;
+                if (ps >= s.size()) return true;
+            }else {
+                pt++;
+            }
+        }
+        
+        return false;
+    }
+};
