class Solution(object):
    def isSubsequence1(self, s, t):
        # create a list to save the index of each letter in t
        listt = [[] for _ in range(26)]
        
        for i in range(len(t)):
            listt[ord(t[i])- 97].append(i)
        # create a list to find the index of each letter of s in t    
        lists = [0 for _ in range(len(s))]
        
        if not s: return True
        if not listt[ord(s[0])-97]: return False # if first letter of s is not in t
        lists[0] = listt[ord(s[0])-97].pop(0) # min. value for first letter
                
        for i in range(1,len(s)):
            if not listt[ord(s[i])-97]: return False # if the letter is not in t
            index, value = self.helper(listt[ord(s[i])-97],lists[i-1])
            if index == -1: return False
            lists[i],listt[ord(s[i])-97]= value, listt[ord(s[i])-97][index+1:]
                    
        return lists == sorted(lists)
      # a helper function to find the index   
    def helper(self, nums, value):
        if value > nums[-1]: return (-1,-1)
        else:
            temp, i = nums[0], 0
            while value > temp and i < len(nums):
                i+=1
                temp = nums[i]
        return (i,temp)
        
    def manys(self,s,t):
        hmaping=[[] for _ in range(26)]
        # pre record the position
        for i in xrange(len(t)):
            hmaping[ord(t[i])- 97].append(i)
        
        # search index
        curidx=-1
        for ch in s:
            if not hmaping[ord(ch)-97] or hmaping[ord(ch)-97][-1]<=curidx:
                return False
            left,right=0,len(hmaping[ord(ch)-97])-1
            while left<right:
                mid=(left+right)/2
                if hmaping[ord(ch)-97][mid]>curidx:
                    right=mid
                else:
                    left=mid+1
            curidx=hmaping[ord(ch)-97][left]
        return True
                
    def isSubsequence(self, s, t):
        """
        :type s: str
        :type t: str
        :rtype: bool
        """
        return self.manys(s,t)
        sidx=tidx=0
        while sidx<len(s) and tidx<len(t):
            if s[sidx]==t[tidx]:
                sidx+=1
            tidx+=1
        return sidx==len(s)
        
        i=0
        for ch in s:
            newi=t.find(ch,i)
            if newi==-1:return False
            i=newi+1
        return True
@@ -21,1233 +21,8 @@
 t):%0A
-    def isSubsequence1(self, s, t):%0A        # create a list to save the index of each letter in t%0A        listt = %5B%5B%5D for _ in range(26)%5D%0A        %0A        for i in range(len(t)):%0A            listt%5Bord(t%5Bi%5D)- 97%5D.append(i)%0A        # create a list to find the index of each letter of s in t    %0A        lists = %5B0 for _ in range(len(s))%5D%0A        %0A        if not s: return True%0A        if not listt%5Bord(s%5B0%5D)-97%5D: return False # if first letter of s is not in t%0A        lists%5B0%5D = listt%5Bord(s%5B0%5D)-97%5D.pop(0) # min. value for first letter%0A                %0A        for i in range(1,len(s)):%0A            if not listt%5Bord(s%5Bi%5D)-97%5D: return False # if the letter is not in t%0A            index, value = self.helper(listt%5Bord(s%5Bi%5D)-97%5D,lists%5Bi-1%5D)%0A            if index == -1: return False%0A            lists%5Bi%5D,listt%5Bord(s%5Bi%5D)-97%5D= value, listt%5Bord(s%5Bi%5D)-97%5D%5Bindex+1:%5D%0A                    %0A        return lists == sorted(lists)%0A      # a helper function to find the index   %0A    def helper(self, nums, value):%0A        if value %3E nums%5B-1%5D: return (-1,-1)%0A        else:%0A            temp, i = nums%5B0%5D, 0%0A            while value %3E temp and i %3C len(nums):%0A                i+=1%0A                temp = nums%5Bi%5D%0A        return (i,temp)%0A        %0A
     

[392. Is Subsequence][Accepted]committed by Victor