1. Target string in source string

strStr

For a given source string and a target string, you should output the first index(from 0) of target string in source string.

If target does not exist in source, just return -1. http://www.lintcode.com/en/problem/strstr/#



In [1]:

    
# Corner case!!!
"" is None









    Out[1]:





False



In [2]:

    
class Solution:
    def strStr(self, source, target):
        # write your code here
        if source is None or target is None:
            return -1
        m = len(source)
        n = len(target)
        for i in range(m-n+1):
            j = 0
            while j < n:
                if source[i+j] != target[j]:
                    break
                j += 1
            if j == n:
                return i
        return -1



In [5]:

    
Solution().strStr('abssss', 'bs')









    Out[5]:





1

Implement strStr function in O(n + m) time.

strStr return the first index of the target string in a source string. The length of the target string is m and the length of the source string is n. If target does not exist in source, just return -1.



In [ ]:

2. Subsets

Given a set of distinct integers, return all possible subsets.



In [12]:

    
class Solution:
    """
    @param S: The set of numbers.
    @return: A list of lists. See example.
    """
    def subsets(self, S):
        # write your code here
        if len(S) == 0:
            return [[]]
        S.sort()
        res = self.subsets(S[:-1])
        ans = []
        for s in res:
            ans.append(s)
            ans.append(s + [S[-1]])
        return  ans



In [14]:

    
Solution().subsets([1,2])









    Out[14]:





[[], [2], [1], [1, 2]]



In [15]:

    
class Solution:
    """
    @param S: The set of numbers.
    @return: A list of lists. See example.
    """
    def subsets(self, S):
        # write your code here
        
        self.results = []
        self.subset = []
        S.sort()
        self.search(S, [], 0)
        return self.results
        
        
    def search(self, S, subset, index):
        if index == len(S):
            self.results.append(subset)
            return
        
        self.search(S, subset + [S[index]], index + 1)
        self.search(S, subset, index + 1)



In [ ]:

    
class Solution:
    """
    @param S: The set of numbers.
    @return: A list of lists. See example.
    """
    def subsets(self, S):
        # write your code here
        
        res = [[]]
        S.sort()
        for i in range(len(S)):
            for j in range(len(res)):
                res.append(res[j] + [S[i]])
        return res

Given a list of numbers that may has duplicate numbers, return all possible subsets



In [21]:

    
class Solution:
    """
    @param S: A set of numbers.
    @return: A list of lists. All valid subsets.
    """
    def subsetsWithDup(self, S):
        # write your code here
        res = [[]]
        S.sort()
        for i in range(len(S)):
            if i == 0 or S[i] != S[i-1]:
                l = len(res)
            for j in range(len(res)-l, len(res)):
                res.append(res[j] + [S[i]])
        return res



In [22]:

    
Solution().subsetsWithDup([1,2,2])









    Out[22]:





[[], [1], [2], [1, 2], [2, 2], [1, 2, 2]]

3. Permutations

Given a list of numbers, return all possible permutations.



In [ ]:



In [ ]:



In [ ]:



In [ ]:



In [ ]:



In [ ]: