lintcode question record 3

Expression Expand Word Break II Partition Equal Subset Sum

String expansion problem, expand according to the number before [] Strings mainly maintain two stacks, one is to expand the number stack and the other is to expand the content stack. The content stack is added [to determine whether to push out all the content to be expanded, and then note that the number may be more than one digit, and the rest does not matter

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

Word segmentation problem, search from the beginning of the string in the array, add it to the stack when found, and then loop pop every time to determine pop Is the string that comes out complete? If it is complete, add the result. If it is incomplete, look for the follow-up. If you can find the follow-up, add it to the stack without continuing to the next cycle. There must be ambiguity here. Can the string in wordDict be reused?

This thing will be very slow when the string is very long and there are many dictionary arrays behind it. I haven’t thought of any optimization algorithm for the time being. There seems to be no such situation in the test data given by lintcode. There is only one special case, so the previous After adding a filter, it passed, and you should also pay attention to python's startwith function

If the parameter is '', it always returns True, which is a bit cheating...

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

Array grouping and summing problem, the question says that the conditions are that many numbers are integers and do not exceed 100, and the length of the array does not exceed 200, that is, let Use dynamic programming to do it, which is a simplified version of the knapsack problem. First find the sum of all numbers. If it is an even number, it can be divided into two groups. Otherwise, it returns false directly, and then divides by 2 to find the final sum of the groups. This value is similar to the knapsack problem. Capacity, the numbers in the array are similar to things that need to be put into a backpack. Different from the backpack problem, the backpack problem requires traversing to the last grid. Here, it only needs that the grid value is equal to this sum. It does not have to be traversed to the last grid.

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

The above is the detailed content of lintcode question record 3. For more information, please follow other related articles on the PHP Chinese website!