I'm trying to solve this problem 514C, in simple terms you are given n strings and m queries, each query consist of a string s, can you find an equal string in the given n strings by changing only one character in s, (all strings consist only of 'a','b', and 'c')
My solution is brute force based: for each query change each character and try to find if it exist in the given strings using a HashSet, but I got a WA in pretest 6 can any one tell me what I'm doing wrong.
You are forgetting that strings s and t must differ in exactly one character. In your submission, you are testing all the possibilities('a', 'b' and 'c', but you should continue when it is equals to s[ j ] ).
Yes you are right, but even after I checked when the strings are equals I still got WA in pretest 6 26380712
It is because you start with if(set.contains(s)) found = true; and there's no reason to search the string s in the initial set, because you have to change exactly one character.
I missed that one while fixing my code, thank's for pointing, but know I get TLE on pretest 18 isn't HashSet.contains() work on log(n)?
I think that the function replace is linear on the size of s. So, your second loop is quadratic on the size of s. The idea in this problem is that you can get hash values for the new strings in constant time, once you know the hash value of s.