Can anyone let me know what the complexity of this problem? I got TLE with O(mnlen(strs)). Here's my code:
class Solution(object): def findMaxForm(self, strs, m, n): """ :type strs: List[str] :type m: int :type n: int :rtype: int """ k = len(strs) if k == 0: return 0 a = *(k+1) b = *(k+1) for i in range(k): a[i+1] = strs[i].count('0') b[i+1] = strs[i].count('1') f = [*(n+1) for i in range(m+1)] for t in range(1, k+1): for i in range(m, -1, -1): for j in range(n, -1, -1): if i >= a[t] and j >= b[t] and f[i][j] < f[i-a[t]][j-b[t]] + 1: f[i][j] = f[i-a[t]][j-b[t]] + 1 return f[m][n]
Yeah, I got TLE with what I think is the same solution (O(nmk) where k is len(strs)) in Python so I rewrote it in C++ and it got accepted. (Although I had a memory limit exceeded for using a dp table that was O(nmk) until I changed it to be O(nm))
@quanhoang I have just increased the time limit, your solution is now accepted.
@1337c0d3r What was the time limit before and what is it now? I had submitted the above code twice and it got accepted both times, in around 3000 ms. And after replacing the wasteful
b[t] with variables
bt set as the first thing in the
t-loop (since they never change inside), it got accepted in around 2200 ms. And after integrating them in the ranges (like
range(m, at-1, -1)) it got accepted in around 1700 ms.
@StefanPochmann The time limit before was around 2 seconds, which is the default time limit. Now I have increased the time limit to around 7 seconds, just to be safe. It seems that Python solutions' runtime can vary a lot depending on the language construct you use.
@1337c0d3r When I ran the test-case that was timing out for me, it said it took 52 ms.
nd 2200 ms.
Thanks Stefan, I was so stupid to calculate a[t] and b[t].
@1337c0d3r There are several other problems that suffer from the same dynamic programming Python table construction TLE like:
- Coin Change
class Solution(object): def coinChange(self, coins, amount): """ :type coins: List[int] :type amount: int :rtype: int """ T = [None] * (amount+1) T = 0 for i in range(1, amount+1): for coin in coins: if i-coin >= 0 and T[i-coin] != None: T[i] = T[i-coin] + 1 if T[i] == None else min(T[i], T[i-coin]+1) return T[-1] if T[-1] != None else -1
- Longest Palindromic Substring
class Solution(object): def longestPalindrome(self, s): """ :type s: str :rtype: str """ best = '' T = [[False for __ in range(len(s))] for _ in range(len(s))] for i in range(len(s)): T[i][i] = True best = s[i] for i in range(len(s)): if i + 1 < len(s) and s[i]==s[i+1]: best = s[i:i+2] T[i][i+1] = True for length in range(3, len(s)+1): for i in range(0, len(s)-length+1): if T[i+1][i+length-1-1] and s[i] == s[i+length-1]: T[i][i+length-1] = True best = s[i:i+length] return best
@zizhengwu I have fixed both of them.
@1337c0d3r And one more
- Perfect Squares
class Solution(object): def numSquares(self, n): """ :type n: int :rtype: int """ T = [i for i in range(n+1)] perfects =  i = 1 for n in range(1, n+1): if n == i*i: perfects.append(i*i) i += 1 for p in perfects: T[n] = min(T[n], T[n-p]+1) return T[n]
Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.