lintcode 題目記錄3

Expression Expand  Word Break II Partition Equal Subset Sum

字元串展開問題，按照[]前的數字展開字元串，主要是維護兩個棧一個是展開個數棧一個是展開內容棧，內容棧添加[用來判斷是否把要展開的內容全部推出，然後要註意數字可能不止一位其他就無所謂了

class Solution:
    # @param {string} s  an expression includes numbers, letters and brackets
    # @return {string} a string
    def expressionExpand(self, s):
        # Write your code here
        nl=[]
        sl=[]
        sc=''
        res=''
        lstr=''
        for i in s:
            if i.isdigit():
                if not lstr.isdigit():
                    sl.append(sc)
                    sc=''
                sc = sc + i
            else:
                if i=='[':
                    nl.append(int(sc))
                    sc = ''
                    sl.append('[')
                elif i==']':
                    n=nl.pop()
                    while len(sl)>0:
                        k=sl.pop()
                        if k== '[':break
                        sc = k+ sc
                    ts=''
                    for j in range(n):ts= ts + sc
                    sc=''
                    if len(nl) > 0:sl.append(ts)
                    else:
                        res = res + ts
                else:
                    if len(nl)>0:
                        sc = sc + i
                    else:
                        res = res + i
            lstr=i
        return res

 Word Break II  

單詞切分問題，在數組重從開頭的字元串開始查找，找到了就加入棧，然後每次迴圈pop  判斷pop出的字元串是否完整，完整加入結果，不完整找後續，能找到後續加入棧，沒有繼續下一次迴圈，這裡又一定歧義，wordDict裡邊的字元串是否可以重覆使用的問題？

這玩意當字元串很長後邊的字典數組很多的時候會很慢，暫時沒想到什麼優化的演算法，lintcode給的測試數據裡邊好像沒有這種情況只有一個特殊情況，所以前邊加了一個過濾算是通過了，還有要註意python的startwith函數 

如果參數是''總是返回True略坑爹····

class Solution:
    # @param {string} s a string
    # @param {set[str]} wordDict a set of words
    def wordBreak(self, s, wordDict):
        # Write your code here
        head=[]
        ss=''
        for i in s:
            if ss=='':
                ss=i
            else:
                if i not in ss:
                    ss = ss + i

        for i in ss:
            flag=False
            for di in wordDict:
                if i in di:
                    flag=True
                    break;
            if not flag:
                return []
        for di in wordDict:
            if di !='' and  s.startswith(di):
                head.append(di)
        if len(head)<1:return []
        cur=s
        res=[]
        while len(head)>0:
            h=head.pop()
            le=len(h.replace(' ',''))
            cur=s[le:]
            if cur == '': 
                res.append(h)
                continue
            for di in wordDict:
                if cur.startswith(di):
                    head.append(h+' '+di)
                    
        return res

Partition Equal Subset Sum

數組分組求和問題，題目說條件很多 數字都是整數不超過100 數組長度不超過200，就是讓用動態規劃來做，就是背包問題的簡化版，先求所有數字的和，為偶數才能分成兩組，否則直接返回false，然後除以2求最終要分組的和，這個值就類似背包問題的容量，數組中的數字就類似要裝進背包的東西，不同於背包問題的是背包問題要遍歷到最後一個格子，這裡只有又格子值與這個和相等就行了，不一定要遍歷到最後一個格子

class Solution:
    # @param {int[]} nums a non-empty array only positive integers
    # @return {boolean} return true if can partition or false
    def canPartition(self, nums):
        # Write your code here
        sum=0
        for n in nums:
            sum = sum +n
        if sum%2!=0:return False
        k=sum//2
        a=[None]*len(nums)
        for i in range(len(nums)):
            a[i]=[0]*k
            
        for i in range(len(nums)):
            for j in range(k):
                if i == 0:
                    a[i][j] = nums[i] if nums[i] < j+1 else 0
                else:
                    if nums[i]> j+1:
                        a[i][j]=a[i-1][j]
                    else:
                        a[i][j]=max(nums[i]+a[i-1][j+1-nums[i]],a[i-1][j])
                        
                if a[i][j] ==k:return True
        return False