Test 7 exceeds the default token size in Golang. I can be the first person to find this?
Use this main instead to pass all tests.
func main() {
scanner := bufio.NewScanner(os.Stdin)
buf:=make([]byte,0,100001)
scanner.Buffer(buf,100001)
scanner.Scan()
original := scanner.Text()
scanner.Scan()
check := scanner.Text()
res := findAllAnagrams(original, check)
fmt.Println(strings.Join(arrayItoa(res), " "))
}
Thanks
def get_mapping(check):
mapping = {}
for char in check:
if char in mapping:
mapping[char] += 1
else:
mapping[char] = 1
return mapping
def valid_anagram_window(window):
for value in window.values():
if value != 0:
return False
return True
def find_all_anagrams(original, check):
left = 0
result = []
right = len(check)
invalid_input = lambda x, y: len(y) > len(x)
if invalid_input(original, check):
return []
while left < len(original) - right + 1:
window = original[left:left+right]
mapping = get_mapping(check)
for char in window:
if char in mapping:
mapping[char] -= 1
else:
continue
if valid_anagram_window(mapping):
result.append(left)
left += 1
return result
def find_all_anagrams(original: str, check: str) → List[int]:
def isAnagram(word1, word2):
# word2 should be sorted already
return sorted(word1) == word2
left = 0
right = len(check)
res = []
check = sorted(check)
while right <= len(original):
if isAnagram(original[left:right], check):
res.append(left)
right += 1
left += 1
return res
My python solution:
from typing import List
from collections import Counter
def find_all_anagrams(original: str, check: str) → List[int]:
if len(check) > len(original): return []
check_counter = Counter(check)
l,r=0, len(check)-1
ans = []
word_counter = Counter(original[:r])
while r < len(original):
word_counter[original[r]] = 1 + word_counter.get(original[r], 0)
if word_counter == check_counter:
ans.append(l)
word_counter[original[l]] -= 1
if word_counter[original[l]] == 0: del word_counter[original[l]]
l += 1
r += 1
return ans
One of these test cases is very sussy and baka.
def isAnagram(w1, w2):
if sorted(w1) == sorted(w2):
return True
else:
return False
def find_all_anagrams(original: str, check: str):
# WRITE YOUR BRILLIANT CODE HERE
res = list()
start, end = 0, len(check)
while end <= len(original):
#print(original[start:end], check)
if isAnagram(original[start:end], check): #simple set equal is not enough!
res.append(start)
start += 1
end += 1
return res
Why is the coding style so different from the others? Can we please have the ability to get rid of the comments in the code? They aren’t really helpful.
I ran into this but I didn’t understand why Test 7 didn’t work at all. Thanks for this. Seems so obvious in hindsight but I didn’t look at main. I just made sure my solution passed on Leetcode.
from typing import List
def find_all_anagrams(original: str, check: str) → List[int]:
# WRITE YOUR BRILLIANT CODE HERE
left, right = 0, len(check)
n = len(original)
res = []
while right <= n:
if right - left == len(check):
if sorted(original[left:right]) == sorted(check):
res.append(left)
left += 1
right += 1
return res
I agree! No one will have time in an interview to write all those comments!
those comments are there for your understanding of the code. so you understand what each line is trying to do. in an interview obviously you dont write it, you just explain to your interviewer what you’re trying to do
What would be the time complexity of such a loop that keeps sorting elements to check values?
My solution works on LeetCode for the same case(Test #1) but fails here. I always gets “0” in the output instead of “0 6” while running same in LC, it works just fine.
def find_all_anagrams(original: str, check: str) -> List[int]:
# WRITE YOUR BRILLIANT CODE HERE
right = 0
anagram = Counter(check)
lenCheck = len(check)
result = []
while right < len(original) - lenCheck + 1:
if right == 0:
tempCounter = Counter(original[right:lenCheck])
else:
tempCounter[original[right-1]] -= 1
tempCounter[original[right+lenCheck-1]] += 1
if anagram == tempCounter:
result.append(right)
print(tempCounter,right )
right += 1
return result
I think the issue here is Counter comparison in different python versions. LC and AM likely have different versions.
Changed in version 3.10: In equality tests, missing elements are treated as having zero counts. Formerly, Counter(a=3) and Counter(a=3, b=0) were considered distinct.
For test case 1 and right = 6, tempCounter is Counter({'c': 1, 'b': 1, 'a': 1, 'e': 0}) and anagram is Counter({'a': 1, 'b': 1, 'c': 1})
anagram == tempCounter would return different result depending on the python version.
I’ve found using a separate class to manage the sliding window makes the impl easy to understand, FYI this is my code:
def __init__(self):
self.container = defaultdict(lambda: 0)
def push(self, c):
self.container[c] += 1
def pop(self, c):
self.container[c] -= 1
if self.container[c] == 0:
self.container.pop(c)
def size(self):
return sum(self.container.values())
def find_all_anagrams(original: str, check: str) -> List[int]:
# WRITE YOUR BRILLIANT CODE HERE
target_dict = Counter(check)
fast = slow = 0
res = []
window = SlidingWindow()
win_size = len(check)
while fast < len(original):
c = original[fast]
window.push(c)
#print(f"checking {c}, win: {window.container}")
if window.size() == win_size:
#print(f"window is full: {win_size}")
if window.container == target_dict:
#print("hit a match")
res.append(slow)
# window is full, pop the leftmost char
window.pop(original[slow])
#print(f"popped {original[slow]}, window is moved: {window.container}")
slow += 1
fast += 1
return res```My solution, using Counter() to for anagrams checking.
def find_all_anagrams(original: str, check: str) → List[int]:
def is_anagrams(s1, s2):
return Counter(s1) == Counter(s2)
check_set = [c for c in check]
window_set = [c for c in original[:len(check_set)]]
res = []
for i in range(len(check_set), len(original)+1):
if is_anagrams(check_set, window_set):
res.append(i - len(check_set))
if i < len(original):
window_set.append(original[i])
window_set.pop(0)
return res
Javascript using Maps to keep count of letter frequency.
No need to iterate over 2 arrays to validate equality
function findAllAnagrams(original, check) {
const checkMap = getFreqMap(check);
const windowMap = new Map();
let l = 0;
const checkLength = check.length;
let matchLength = 0;
const res = [];
if(original.length < checkLength) return [];
for(let r = 0; r < original.length; r++) {
// is window length reached?
if(r - l > checkLength - 1) {
const leftChar = original.charAt(l);
// leftSubstract
if(windowMap.has(leftChar)) {
const count = windowMap.get(leftChar) - 1;
windowMap.set(leftChar, count);
if(count < checkMap.get(leftChar)) matchLength -= 1;
}
l += 1;
}
// right Add
const rightChar = original.charAt(r);
if(checkMap.has(rightChar)) {
if(!windowMap.has(rightChar)) windowMap.set(rightChar, 0);
const count = windowMap.get(rightChar) + 1;
windowMap.set(rightChar, count);
if(count <= checkMap.get(rightChar)) matchLength += 1;
if(matchLength === checkLength) res.push(l);
}
}
return res;
}