expression expand  word break ii partition equal subset sum
 expression expand 
字符串展开问题，按照[]前的数字展开字符串，主要是维护两个栈一个是展开个数栈一个是展开内容栈，内容栈添加[用来判断是否把要展开的内容全部推出，然后要注意数字可能不止一位其他就无所谓了
class solution:# @param {string} s  an expression includes numbers, letters and brackets# @return {string} a stringdef expressionexpand(self, s):# write your code herenl=[]         sl=[]         sc=''res=''lstr=''for i in s:if i.isdigit():if not lstr.isdigit():                     sl.append(sc)                     sc=''sc = sc + ielse:if i=='[':                     nl.append(int(sc))                     sc = ''sl.append('[')elif i==']':                     n=nl.pop()while len(sl)>0:                         k=sl.pop()if k== '[':breaksc = k+ sc                     ts=''for j in range(n):ts= ts + sc                     sc=''if len(nl) > 0:sl.append(ts)else:                         res = res + tselse:if len(nl)>0:                         sc = sc + ielse:                         res = res + i             lstr=ireturn 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 wordsdef wordbreak(self, s, worddict):# write your code herehead=[]         ss=''for i in s:if ss=='':                 ss=ielse:if i not in ss:                     ss = ss + ifor i in ss:             flag=falsefor di in worddict:if i in di:                     flag=truebreak;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)continuefor 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 falsedef canpartition(self, nums):# write your code heresum=0for n in nums:             sum = sum +nif sum%2!=0:return false         k=sum//2a=[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 0else: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 truereturn false
以上就是lintcode 题目记录3的详细内容。