1.买水果

public static int checkWinner (List<List<String>> codeList, List<String> shoppingCart) {}

说的是小明要帮公司买水果，给了一个codeList， 里面装的是他买的水果，给了一个shoppingCart里面装的是target水果，目标是检查codelist里的水果顺序是否和shoppingCart里的顺序匹配。

注意的是只有codelist中的所有链表的item之后加起来小于等于shoppingcart里item之和才可能返回1。 另外在codelist中有可能出现item时 "anything"， 它可以和任意的水果匹配。

1.买水果
public static int checkWinner (List<List<String>> codeList, List<String> shoppingCart) {}
说的是小明要帮公司买水果，给了一个codeList， 里面装的是他买的水果，给了一个shoppingCart里面装的是target水果，目标是检查codelist里的水果顺序是否和shoppingCart里的顺序匹配。
注意的是只有codelist中的所有链表的item之后加起来小于等于shoppingcart里item之和才可能返回1。 另外在codelist中有可能出现item时 "anything"， 它可以和任意的水果匹配。
Ex1: 
codelist:
[
    [apple, apple],
    [orange, banana, orange]
]. 
shoppingCart: [orange, apple, apple, orange, banana, orange].
return 1, 因为codelist里的顺序和shoppingcart里除了第一个orange之后的水果顺序匹配. 

Ex2: 
codelist:
[
    [orange, banana, orange]，
    [apple, apple]
]
shoppingCart: [orange, apple, apple, orange, banana, orange]
return 0, 因为codeList里的顺序和shoppingcart没法匹配。

Ex3: .
codelist:
[
    [apple, apple],
    [orange, banana, orange],
    [pear, orange, grape].
]. 
shoppingCart: [orange, apple, apple, orange, banana, orange, pear, grape]
return 0, 因为codelist里最后一个[pear, orange, grape]中的orange没法和shoppingcart里的水果匹配。

Ex4:
codeList:
[
    [apple, apple],
    [orange, anything, orange]
] 
shoppingCart:
[orange, apple, apple, orange, mango, orange]
return 1。

思路：用dp, 大概思想就是 我循环codesList里面的每一个codes然后去跟shopping cart去match, 如果match到了，我就看这个shopping item前面有没有match到第i-1个的codes。

拿第一个来举例：

第一个循环后，应该是dp = [0, 0, 1, 1, 1, 1]

第二个循环后是 dp = [0, 0, 1, 1, 1, 2]

然后我们比较最后一个位置跟codesList的长度相不相等就行了。

dp[i]代表的是shoppingCart种的第i个item最多能match完codesList种的第几个。如果能match完那么我们就return True

第二种是kaishen的更优的解法。首先意识到这个codesList只能单调递增。所以其实我们直接循环shoppingCart种的item来match codesListz中的item就完了。然后用一个cur来记录match到codesList的第几层了。非常棒的解法，鼓掌！

class Solution():
    def buyFriut(self, codesList, shoppingCart):
        dp = [0]*len(shoppingCart)

        for i, codes in enumerate(codesList):
            l = len(codes)
            for j in range(len(shoppingCart)):
                # if match the code dp + 1
                if j <= (len(shoppingCart) - l) and self.isMatch(codes, shoppingCart[j:j+l]) and dp[j-1]==i:
                    dp[j+l-1] = dp[j+l-2] + 1
                # if previous char have matched, propogate to the end
                if j >= 1 and dp[j-1]:
                    dp[j] = max(dp[j], dp[j-1])
        return dp[-1] == len(codesList)

    def isMatch(self, codes, cartSeq):
        for i in range(len(codes)):
            if codes[i] != 'anything' and codes[i]!= cartSeq[i]:
                return False
        return True


#better Solution
class Solution():
    def buyFriut(self, codesList, shoppingCart):
        dp = [0]*len(shoppingCart)
        cur = 0
        for i in range(len(shoppingCart)):
            l = len(codesList[cur])
            # if match the code dp + 1
            if i>=l and self.isMatch(codesList[cur], shoppingCart[i-l+1:i+1]) and dp[i-l]==cur:
                cur += 1
                dp[i] = cur
            # if previous char have matched, propogate to the end
            if i >= 1 and dp[i-1]:
                dp[i] = max(dp[i], dp[i-1])
        return dp[-1] == len(codesList)

    def isMatch(self, codes, cartSeq):
        for i in range(len(codes)):
            if codes[i] != 'anything' and codes[i] != cartSeq[i]:
                return False
        return True

s = Solution()
codesList = [
    ['apple', 'apple'],
    ['orange', 'banana', 'orange']
]
shoppingCart = ['orange', 'apple', 'apple', 'orange', 'banana', 'orange']
print s.buyFriut(codesList, shoppingCart)
codesList = [
    ['orange', 'banana', 'orange'],
    ['apple', 'apple']
]
shoppingCart = ['orange', 'apple', 'apple', 'orange', 'banana', 'orange']
print s.buyFriut(codesList, shoppingCart)
codesList = [
    ['apple', 'apple'],
    ['orange', 'banana', 'orange'],
    ['pear', 'orange', 'grape']
]
shoppingCart = ['orange', 'apple', 'apple', 'orange', 'banana', 'orange', 'pear', 'grape']
print s.buyFriut(codesList, shoppingCart)
codesList = [
    ['apple', 'apple'],
    ['orange', 'anything', 'orange']
]
shoppingCart = ['orange', 'apple', 'apple', 'orange', 'mango', 'orange']
print s.buyFriut(codesList, shoppingCart)