[ 1 ]  [ 2 ]  [ 3 ] 
Programming Problems/Preprocessing

list of words 가 주어졌을 때, 두 단어를 조합해서 palindrome 만들기 Q

{bat,tab,cat} 이 있으면 bat tab 이 palindrome이므로 존재한다.

중복도 존재가능하다


우선 두개를 고르는 경우의 수가 N^2 개 이므로, palindrome인지 검사하는 비용 K를 고려하면 O(N^2K) 알고리즘이다.


그런데 성질을 조금 더 관찰해 보면 우선 두개를 합쳐서 palindrome이 되려면 1앞 == 2뒤 또는 1뒤 == 2앞이어야 한다. 그래야 합치니까..


aaaz aaab aaac aaad aaae 이 경우에 결국 모든 조합을 다 테스트해 보니 최악의 경우는 같다



답 : 트라이 프리프로세싱을 할 수 있다..!!


of 8 votes

1) Add the first word to the trie ( A B)
2) Take the second word (D E E D B A) and reverse it (A B D E E D) 
3) See how many letters in the reversed word you can match in the trie (the first 2) 
4) Take the rest of the string (D E E D) see if it is a palindrome if it is you are done return true 
5) add the second word to the trie (D E E D B A)
6) go back to step 2 with the next word 
7) when out of words return false

그리고 반대의 경우 성립하지 않을 수도 있으므로 



1
of 1 vote

@DRADM, this will not work if first word to be inserted in trie is DEEDBA. And second word comes as AB so if you reverse it (BA) and try to compare in trie. You will end up returning false. 

In this scenario, apart from reversing word (BA) and checking trie, we have to take original word (AB) and try to match with the reverse of words which are inserted in tried (DEEDBA) so that will match here.

But it will be expensive to lookup word(AB) in reverse side in trie (DEEDBA).

So to simplify, we need to maintain two tries, when we insert DEEDBA in one trie, we will add ABDEED in second trie. And then for second word first we try to lookup reverse (BA) in first trie and original (AB) in second trie

Here it will be there in second trie and we can apply rest of the logic

뒤집은 트리도 보관한다!!


그니깐 두 트리에서 최대한 따라간 후에 남는 부분(어느 쪽이든) 을 테스트 해 본다.


시간복잡도가 O(NK) 라는데 그 이유는 더 생각해봐야 할듯..