# Ones and Zeroes Python O(m*n*len(strs)) TLE

• 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 = [0]*(k+1)
b = [0]*(k+1)

for i in range(k):
a[i+1] = strs[i].count('0')
b[i+1] = strs[i].count('1')

f = [[0]*(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]
``````

• I wrote such a solution in C++ and it got accepted.

• 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 `a[t]` and `b[t]` with variables `at` and `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:

1. 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] = 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
``````
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

1. 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]

``````

• @zizhengwu Fixed.

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.