It "LOOKS LIKE" your DFS only visited each email account once, by using a "visited" list. But you didn't remove the visited "neighbor" from the emails_accounts_map, so the block of code:
'''
if visited_accounts[i]:
return
'''
It "LOOKS LIKE" your DFS only visited each email account once, by using a "visited" list. But you didn't remove the visited "neighbor" from the emails_accounts_map, so the block of code:
'''
if visited_accounts[i]:
return
'''
'''
class Solution(object):
def maximumSwap(self, num):
num = str(num)
n = len(num)
index_of_max_from_right = [0] * n
swapped_digits = list(num)
# scan from right to left, find the index of the biggest digit to num[i]'s right (including num[i])
for i in xrange(n - 1, -1, -1):
# second condition is ">=" because you want to swap the smaller digit with the right most bigger digit
if i < n - 1 and num[index_of_max_from_right[i + 1]] >= num[i]:
index_of_max_from_right[i] = index_of_max_from_right[i + 1]
else:
index_of_max_from_right[i] = i
the_index_to_swap = None
j = 0
while j < n:
if num[index_of_max_from_right[j]] > num[j]:
the_index_to_swap = index_of_max_from_right[j]
break
j += 1
if the_index_to_swap != None:
swapped_digits[the_index_to_swap] = num[j]
swapped_digits[j] = num[the_index_to_swap]
return int(''.join(swapped_digits))
'''
If this question appeared two years ago, it would probably end up being a hard question. Coming up with the O(NK) time DP solution is not something you can always expect.
I guess a more clear explanation for "* (n + 1)" is each chunk has at lease n + 1 chars when the frame is formed at first, not necessarily "for the for loop" as you said.
Assume the most frequent letter(s) is with count k, then there are two cases:
When the whole frame is "loose" -- when there is still unused idle time in each chunk, result = (c[25] - 1) * (n + 1) + 25 - i where "25 - i" simply counts how many letters are with count k and n + 1 is the length of each chunk. Since we have k (in this case k == c[25]) chunks, the total length of the first k - 1 chunks == (k - 1) * (n + 1). For the last chunk, we don't need the "whole chunk" (i.e., if the chunk is "ABXXX", we only will need the "AB". Because there are no more "less frequent letters" left so we can remove the last three spaces)
When the frame is "dense" (fully filled), the length of each chunk > n + 1. In this case it could be: a) initially the number of letters with count k is > n + 1 so the frame is already "fully filled without space left", or 2) the length of each chunk is > n + 1 after insertion. We still calculate the total length by adding up all the chunks, and it will == the length of the task at last.
Here is my Python version:
'''
def leastInterval(self, tasks, n):
c = [0] * 26
for task in tasks:
c[ord(task) - ord('A')] += 1
c.sort()
i = 25
while i >= 0 and c[i] == c[25]:
i -= 1
return max(len(tasks), (c[25] - 1) * (n + 1) + 25 - i)
'''
Every time your iterative solution inspires me. It shows a deep, thorough understanding of Tree data structure
The graph is an undirected graph, and somehow the test cases are written like directed graph so your recursion "clone(neighbor)" works.
Anyway, this problem looks so weird to me...
You are right about the maximum number of extra chars. I see mathematically, the limit value for total chars needed is 3 * (n - 1) when n goes towards infinitely great.
But I still wonder how you can manage to code it :)
Sorry I didn't make it clear...
Everybody knows how to calculate n/2 + n/4 + n/8 + ... + 4 + 2 + 1 since it is a simple geometric sequence. I was saying it has O(logN) items whereas the number of items decides the number of loops (in your linked-list case, the concatenation of nodes).
However, if you can prove that each number needs exactly three extra chars, then we can ignore, jump out of the above discussion because what matters then will be the total number of operations, which is the sum of (n/2 + n/4 + n/8 + ... + 4 + 2 + 1).
@lixx2100 correct me if I am wrong
At first, n/2 + n/4 + ... + 4 + 2 + 1 is O(logN) time, not O(N).
Second, I don't know how you jump to the conclusion that one number only needs one "(", one ")" and one ",". If you could give logical deduction I would really appreciate.
Third, the string concatenation surely takes O(N) because we need to recreate a new string. In terms of using doubly-linked list, you need to justify the above point ("3 extra" nodes for each number), otherwise you cannot guarantee how many "(" or ")" you need to put on each side of the number.
So far I've only seen lots of O(nlogn) solutions...
I think in terms of O(n), you need to figure out how many parentheses you need to add on the left/right of each number.
Using backtracking will always need O(logn) times of looping through the whole list.