class Solution(object):
    def strStr(self, haystack, needle):
        """
        :type haystack: str
        :type needle: str
        :rtype: int
        """
        if not needle:
            return 0
        if haystack == needle:
            return 0

        for i in range(len(haystack)):
            subStr = ''.join(haystack[i : i + len(needle)])
            if len(needle) > len(subStr): #在输入的两个字符很长的情况下，有可能存在资源消耗过大，因此先用长度做简单判断
                return -1

            if subStr == needle:
                return i
        return  -1

class Solution(object):
    def removeDuplicates(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        if not nums:
            return 0
        if len(nums) < 2:
            return 1
        
        index = 0
        for i in range(1, len(nums)):
            if nums[i] != nums[index]:
                index = index + 1
                nums[index] = nums[i]

        return index + 1

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution(object):
    def mergeTwoLists(self, l1, l2):
        """
        :type l1: ListNode
        :type l2: ListNode
        :rtype: ListNode
        """
        if not l1:
            return l2
        if not l2:
            return l1
        if l1.val < l2.val:
            l1.next = self.mergeTwoLists(l1.next, l2)
            return l1
        else:
            l2.next = self.mergeTwoLists(l1, l2.next)
            return l2

class Solution(object):
    def isValid(self, s):
        """
        :type s: str
        :rtype: bool
        """
        matchPairs = {
            '(':')',
            '[':']',
            '{':'}',
            ')':'(',
            ']':'[',
            '}':'{'}

        stack = []
        if len(s) % 2 != 0:
            return False
        
        for char in s:
            if stack and matchPairs[stack[-1]] == char:
                stack.pop()
            else:
                stack.append(char)
        
        return 0 == len(stack)