could you give some comments on what you're trying to do? But for the TLE part, it seems that its because your algorithm runs in O(n^2) which does not meet the time requirements (I believe you need to beat O(n)).
ifanchu
@ifanchu
Posts made by ifanchu

RE: Shortest Palindrome  Time Limit Exceeded

RE: My 2 lines solution in Python
I think you're right, but if we use xrange() in python2 and range() in python3 (which uses generator), maybe we can define it as space O(1)?
Let's assume the above is true, then using a single str variable and then loop through the given string one using xrange() might be actually space O(1)?
Anyway, I don't think OJ would catch this~lol 
RE: My 2 lines solution in Python
Just curious, the question asked "not to use extra space", so your
index = [i for i, x in enumerate(s) if x == ' ']
is not an extra space? This algorithm seems to me a space complexity O(n) solution where the question asked for space O(1) solution?

RE: Memory limit exceeded for this simple Python solution which works on my laptop
I guess your solution is incorrect, please try the following test cases
Your method
convertToTile(52) = AZ which is correctbut
convertToTitle(53) = AAA is incorrect, the correct answer is BA
Another few examples
input your answer correct answer
54 AAB BB
701 AAAAAAAAAAAAAAAAAAAAAAAAAAY ZY
702 AAAAAAAAAAAAAAAAAAAAAAAAAAZ ZZAnother test case OJ uses is 2147483647, your method hangs my desktop...anyway, the answer for this test case is 'FXSHRXW'
Please note that the title after AZ is BA, not AAA
Hope this helps. 
Python wrong answer?
Hi all,
here is a simple python code for this question, but I can't figure out a test case
class Solution: # @param num, a list of integers # @return a string def largestNumber(self, num): num = [str(x) for x in num] num.sort(cmp=lambda x, y: cmp(y+x, x+y)) ret = ''.join(num) return ret.lstrip('0') or '0'
The idea is simple, first I convert all int in num to strings, then provide a custom compare function. In this lambda function, just concatenate and compare (y+x) and (x+y, the reason to switch (x+y) and (y+x) is because we want this array to be sorted in decreasing order.
For example,
cmp(22, 221) > should form 22221 (because 22221>22122), hence cmp(22,221) == 1
Most of the test cases run through fine but the longest test case
[6306,9385,7536,3462,4798,5422,5529,8070,6241,9094,7846,663,6221,216,6758,8353,3650,3836,8183,3516,5909,6744,1548,5712,2281......]
Failed saying "Wrong Answer" and there is no Output.
I tried this test case on my own machine and the function works perfectly.
I guess there is something wrong with the system for python? 
RE: Can anyone pass test using Python
I just passed this using Python, here is the AC'ed python code for your reference.
class Solution: # @param S, a string # @param L, a list of string # @return a list of integer def findSubstring(self, S, L): """ The idea is very simple, use bruteforce with hashing. First we compute the hash for each word given in L and add them up. Then we traverse from S[0] to S[len(S)  total_length], for each index, if the first substring in L, then we compute the total hash for that partition, if hashes match, then we have a match. """ if S is None or L is None or len(L) == 0: return [] # the length of each word len_of_word = len(L[0]) # the length of entire substring total_length = len_of_word * len(L) # use a set to reduce lookup time word_set = set(L) # total hash for the given list of words target_hash = 0 for item in L: target_hash += hash(item) ret = [] for start in xrange(len(S)  total_length + 1): if S[start:start+len_of_word] not in word_set: continue end = start + total_length  1 test_hash = 0 for walker in xrange(start, end + 1, len_of_word): substring = S[walker:walker + len_of_word] # early termination if any of the substring not in set if substring not in word_set: break test_hash += hash(substring) if test_hash == target_hash: ret.append(start) return ret

RE: Timeout. is there a faster solution
you are right, I removed those text~

RE: Is there a better algorithm than what i give
My accepted DP solution in python for your reference, the code might not be the most concise but I think it is very clear and easy to understand.
class Solution: # @return a boolean def isInterleave(self, s1, s2, s3): """ The idea is a straightforward Dynamic Programming, based on the observation that s3 is an interleaving string of s1 and s2 iff s3[0] == s1[0] or s3[0] == s2[0], we can draw a recursion tree for this, then the algorithm is: Keep i1, i2, i3 as the current index for s1, s2 and s3, all starting from 0. Remove 1 char from s3 at a time, and remove the same char from s2 or s3, if s1[i1] and s2[i2] are the same as s3[i3], we need to consider 2 possibilities which are 1. s3[i3+1] is a interleaving string of s1[i1:] and s2[i2+1:] or 2. s3[i3+1] is a interleaving string of s1[i1+1:] and s2[i2:] The algorithm can be described as: 1. i1, i2, i3 start from 0 2. if remaining s3 is equal to either remaining s1 or s2, we have a match 3. else, if the first char of s3 not equal to any of the first char or s1 or s2, this is a no match 4. else, if the first char of s3 equal to both of the first char of s1 and s2, we have the abovementioned 2 possibilities 5. else, if the first char of s3 equal to the first char of s1, then we move i3 and i1 to the right by 1 6. else, if the first char of s3 equal to the first char of s2, we move i3 and i2 to the right by 1 Just like typical DP problem, there will be a handful of overlapping subproblems, so we keep a dp_table to store the intermediate results. """ def _is_interleave(s1, s2, s3, i1, i2, i3, dp_table): """ i1, i2 and i3 are the current index we are considering for s1, s2 and s3, respectively. """ token = (i1, i2, i3) if token in dp_table: return dp_table[token] if s3[i3:] == s1[i1:] or s3[i3:] == s2[i2:]: # s3 is equal to one of the remaining string dp_table[token] = True elif i1 == len(s1) or i2 == len(s2): # if any of the string is exhausted and the above if statement is False, then it is False. Because if s1 exhausted, and s3 != s2, then s3 must not be an interleaving string of s1 and s2; and vice versa dp_table[token] = False elif s3[i3] != s1[i1] and s3[i3] != s2[i2]: # if the first char of s3 not equal to either first char dp_table[token] = False elif s3[i3] == s1[i1] == s2[i2]: dp_table[token] = \ _is_interleave(s1, s2, s3, i1 + 1, i2, i3 + 1, dp_table) \ or _is_interleave(s1, s2, s3, i1, i2 + 1, i3 + 1, dp_table) elif s3[i3] == s1[i1]: dp_table[token] = _is_interleave(s1, s2, s3, i1 + 1, i2, i3 + 1, dp_table) elif s3[i3] == s2[i2]: dp_table[token] = _is_interleave(s1, s2, s3, i1, i2 + 1, i3 + 1, dp_table) else: assert False return dp_table[token] if len(s3) != len(s1) + len(s2): return False return _is_interleave(s1, s2, s3, 0, 0, 0, {})