leetcode 392

Partho Biswas · Partho Biswas · commit 7426332c2751 · 2019-11-09T00:34:18.000+06:00
diff --git a/README.md b/README.md
@@ -279,7 +279,7 @@ I have solved quite a number of problems from several topics. See the below tabl
 |03| [1007. Minimum Domino Rotations For Equal Row](https://leetcode.com/problems/minimum-domino-rotations-for-equal-row/)| [Python](leetcode.com/python/Minimum_Domino_Rotations_For_Equal_Row.py)| [Official](https://leetcode.com/problems/minimum-domino-rotations-for-equal-row/solution/), [Article 01](https://leetcode.com/problems/minimum-domino-rotations-for-equal-row/discuss/252242/JavaC%2B%2BPython-Different-Ideas)| Medium | 📌 Hard to spot if it is a Greedy |
 |04| [406. Queue Reconstruction by Height](https://leetcode.com/problems/queue-reconstruction-by-height/)| [Python](leetcode.com/python/406_Queue_Reconstruction_by_Height.py)| [Article 1](https://leetcode.com/problems/queue-reconstruction-by-height/discuss/89345/Easy-concept-with-PythonC%2B%2BJava-Solution), [Article 2](https://leetcode.com/problems/queue-reconstruction-by-height/discuss/89359/Explanation-of-the-neat-Sort%2BInsert-solution) | Medium | 📌 Fundamentals |
 |05| [621. Task Scheduler](https://leetcode.com/problems/task-scheduler/)| [Python](leetcode.com/python/621_Task_Scheduler.py)| [Ex 1](https://leetcode.com/problems/task-scheduler/discuss/190390/Can-anyone-explain-to-me-what-the-problem-is-asking), [Ex 2](https://leetcode.com/problems/task-scheduler/discuss/130786/Python-solution-with-detailed-explanation), [Vid 1](https://www.youtube.com/watch?v=hVhOeaONg1Y) | Medium | 📌 Extremely tricky. Not done. Check later |
-|06| [392. Is Subsequence](https://leetcode.com/problems/is-subsequence/)| [Python](leetcode.com/python/392_Is_Subsequence.py)| [Ex 1](https://leetcode.com/problems/is-subsequence/discuss/87264/Easy-to-understand-binary-search-solution) | Easy | 📌  |
+|06| [392. Is Subsequence](https://leetcode.com/problems/is-subsequence/)| [Python](leetcode.com/python/392_Is_Subsequence.py)| [Ex 1](https://leetcode.com/problems/is-subsequence/discuss/87264/Easy-to-understand-binary-search-solution), [Ex 3](https://leetcode.com/problems/is-subsequence/discuss/87302/Binary-search-solution-for-follow-up-with-detailed-comments/144323) | Easy | 📌  |
 
 
 ### [Dynamic Programming](https://www.educative.io/courses/grokking-dynamic-programming-patterns-for-coding-interviews)
diff --git a/leetcode.com/python/392_Is_Subsequence.py b/leetcode.com/python/392_Is_Subsequence.py
@@ -3,6 +3,8 @@
 
 # Using Binary search
 class Solution(object):
+
+    # Code 01
     def createMap(self, s):
         # create a map. key is char. value is index of apperance in acending order.
         posMap = defaultdict(list)
@@ -22,14 +24,29 @@ def isSubsequence(self, s, t):
         for char in s:
             if char not in posMap: return False
             charIndexList = posMap[char]
-            # try to find an index that is larger than or equal to lowBound
-            i = bisect_left(charIndexList, lowBound)
+            # try to find an index that is larger than or equal to lowBound. Means, it returns the index of the first occurrence of lowBound in charIndexList
+            i = bisect_left(charIndexList, lowBound)     # https://www.geeksforgeeks.org/binary-search-bisect-in-python/
             if i == len(charIndexList): return False
             lowBound = charIndexList[i] + 1
         return True
 
+    # Code 02
+    # def isSubsequence(self, s, t):
+    #     idx = defaultdict(list)
+    #     for i, c in enumerate(t):
+    #         idx[c].append(i)
+    #     prev = 0
+    #     for i, c in enumerate(s):
+    #         j = bi.bisect_left(idx[c], prev)
+    #         if j == len(idx[c]): return False
+    #         prev = idx[c][j] + 1
+    #     return True
+
+
+
+
 
-# Using  Two Pointer
+    # Using  Two Pointer
 # class Solution(object):
 #     def isSubsequence(self, s, t):
 #         """
@@ -53,6 +70,6 @@ def isSubsequence(self, s, t):
 
 sol = Solution()
 s = "abc"
-t = "ahbgdca"
+t = "habgdca"
 out = sol.isSubsequence(s, t)
 print('Res: ', out)
