<jupyter_start><jupyter_text>1.  Target string in source string  strStrFor 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/<jupyter_code># Corner case!!!
"" is None
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
Solution().strStr('abssss', 'bs')<jupyter_output><empty_output><jupyter_text>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.  2. SubsetsGiven a set of distinct integers, return all possible subsets.<jupyter_code>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
Solution().subsets([1,2])
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)
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<jupyter_output><empty_output><jupyter_text>* Given a list of numbers that may has duplicate numbers, return all possible subsets<jupyter_code>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
Solution().subsetsWithDup([1,2,2])<jupyter_output><empty_output>
{'fraction_non_alphanumeric': 0.11653290529695023, 'fraction_numerical': 0.007383627608346709, 'mean_word_length': 1.871889400921659, 'pattern_counts': {'":': 0, '<': 14, '<?xml version=': 0, '>': 13, 'https://': 0, 'lorem ipsum': 0, 'www.': 1, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '3', 'dir': 'jupyter-structured-clean-dedup', 'id': '130617', 'license': 'MIT', 'n_tokens_mistral': 974, 'n_tokens_neox': 948, 'n_words': 328, 'path': '00_strStr.ipynb', 'repo_name': 'dinrker/Algorithms_DataStructures', 'size': '3115'}