myaw's blog

By myaw, history, 3 years ago, In English,

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.

submission

 
 
 
 
  • Vote: I like it
  • 0
  • Vote: I do not like it

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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 ] ).

  • »
    »
    3 years ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    Yes you are right, but even after I checked when the strings are equals I still got WA in pretest 6 26380712

    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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.

      • »
        »
        »
        »
        3 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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)?

        • »
          »
          »
          »
          »
          3 years ago, # ^ |
          Rev. 2   Vote: I like it +5 Vote: I do not like it

          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.

          • »
            »
            »
            »
            »
            »
            3 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            Yeah exactly, for some reason I thought it work's in O(1) because I used StringBuilder, any way thank's a lot, I appreciate your help.