It seems that coding tests are conducted overseas in interviews with engineers, and in many cases, the main thing is to implement specific functions and classes according to the theme.
Apparently, many engineers take measures on the site called LetCode.
It is a site that trains the algorithmic power that can withstand the coding test that is being done in the early story, and it is an inevitable path for those who want to build a career at an overseas tech company.
I wrote it in a big way, but I have no plans to have such an interview at the moment.
However, as an IT engineer, it would be better to have the same level of algorithm power as a person, so I would like to solve the problem irregularly and write down the method I thought at that time as a memo.
I'm solving it with Python3.
Leet Code Table of Contents Starting from Zero
Last time Leet Code Day 65 "560. Subarray Sum Equals K" starting from zero
Right now, I'm prioritizing the Medium of the Top 100 Liked Questions. I solved all Easy, so if you are interested, please go to the table of contents.
Twitter I'm doing it.
** Technical Blog Started! !! ** ** I think the technology will write about LetCode, Django, Nuxt, and so on. ** This is faster to update **, so please bookmark it!
438. Find All Anagrams in a String
The difficulty level is Medium. Excerpt from Top 100 Liked Questions.
Given the string s and the non-empty string p, the problem is to find all the starting indexes of the p's anagram in the s.
Strings consist of lowercase letters only, and both s and p lengths must not exceed 20,100.
The order of output does not matter.
Example 1:
Input: s: "cbaebabacd" p: "abc"
Output: [0, 6]
Explanation: The substring with start index = 0 is "cba", which is an anagram of "abc". The substring with start index = 6 is "bac", which is an anagram of "abc".
Example 2:
Input: s: "abab" p: "ab"
Output: [0, 1, 2]
Explanation: The substring with start index = 0 is "ab", which is an anagram of "ab". The substring with start index = 1 is "ba", which is an anagram of "ab". The substring with start index = 2 is "ab", which is an anagram of "ab".
You need to clean up the starting index of the anagram.
The algorithm called Sliding Window seems to be famous as a solution, and I plan to write a separate article.
It's a word I've heard on the network, but I've never heard it on an algorithm.
However, what I tried to imitate the logic is as follows
import collections
class Solution:
def findAnagrams(self, s: str, p: str) -> List[int]:
len_s,len_p,set_p,ans = len(s),len(p),Counter(p),[]
for i in range(len_s-len_p+1):
if Counter(s[i:i+len_p]) == set_p:
ans.append(i)
return ans
# Runtime: 7868 ms, faster than 7.31% of Python3 online submissions for Find All Anagrams in a String.
# Memory Usage: 14.8 MB, less than 69.94% of Python3 online submissions for Find All Anagrams in a String.
It was so late that I wondered what happened ...
For the time being, I tried to understand by looking at the discussion.
class Solution:
def findAnagrams(self, s: str, p: str) -> List[int]:
LS, LP, S, P, A = len(s), len(p), 0, 0, []
if LP > LS: return []
for i in range(LP): S, P = S + hash(s[i]), P + hash(p[i])
if S == P: A.append(0)
for i in range(LP, LS):
S += hash(s[i]) - hash(s[i-LP])
if S == P: A.append(i-LP+1)
return A
Then the answer is like this.
Looking at the code, I'm using a hashmap instead of counter, and the rest doesn't seem to change much.
Looking at the speed for the time being ...
Runtime: 68 ms, faster than 99.89% of Python3 online submissions for Find All Anagrams in a String.
Memory Usage: 14.9 MB, less than 42.94% of Python3 online submissions for Find All Anagrams in a String.
！？
It's ridiculously fast ...
If you think about it, turning Counter for each element is obviously inefficient, isn't it?
Turning all the elements each time with a for statement and returning with dic is a rather bad implementation method that the more elements there are, the slower it becomes dramatically.
However, there was no idea to put it in HashMap ... If you look at the discuss, you can come across this kind of idea, so it's important to take a closer look.
So that's it for this time. Thank you for your hard work.
Recommended Posts