Given a string S and string T, implement a function search(string s, string t) that returns all occurrences of T or T's permutations in S. Assume that characters in S and T comprise of only lower and upper case English letters.

Question

Sigiloso · Accepted Answer

Setup two integer arrays with length of 52. Iterate through characters in T, count the occurrence of each character and store the frequencies in the array. Iterate the first T.length() letters of S and count the frequency in the other array. From there, increment the new character and decrement the last character until you reach the end of the string S. (Sliding window approach). Time complexity: O(N + M) where N = length of S and M = length of T

Sigiloso · Answer

The answer above seems incomplete as it does not consider all the permutations of T, which are about n! (n being the length of T). In my opinion, what I would do is find the permutation of T then by length find their occurrences in S.

Sigiloso · Answer

That would be very inefficient. As you mentioned you have n! Permutation by doing so your time complexity would be about n*n! The first answer is correct and complete. You don’t need to print out all of the permutation. You can just have a hash map with all characters of S and compare each strings in the sliding window. If a string has all characters of T in the hash S then you good.

Google

Pergunta de entrevista da empresa Google

Respostas da entrevista

Empresas seguidas

Buscas de vagas