가장 긴 문자열

Question

그래서 나는 최근 인터뷰에서이 질문이 있어요 한 번에 한 문자 씩 입력 문자열의 앞과 뒤에 추가합니다. 새 단어도 모두 사전에 표시되어야합니까?

예는 : 입력 = DICT = {모자, 채팅, 채팅, 쥐, 문신, 문신, chatats}

반환 '채팅'때문에 '에서'에서 -> 모자 -> 채팅 ->이

를 채팅

나는 bruteforce를 사용하여 - z의 모든 문자를 입력 문자열의 앞뒤에 추가하려고 시도했습니다. 새 문자열이 있으면 앞뒤로 26자를 다시 입력하여 결국 최종 문자열.

매번 26 글자 앞뒤로 강요하지 않으면이 문제를 해결하는 데 더 효율적인 방법이 있는지 궁금합니다.

입력란이 입력 문자열을 변경하는 길이보다 1 큰 항목의 하위 문자열로 입력 문자열이 존재하면 입력 문자열에서 입력 하위 문자열을 삭제하십시오.

예 : 1 반복 한 후, 딕셔너리는 것 = {H, 채팅, R, T, 문신, chatats 채팅}

을 그리고 우리는 또한 각 항목에 대해 길이 변수가 원래 길이의 트랙을 유지하는 것 항목의. 그러나 이것이 올바른 접근 방식인지 확실하지 않다고 생각합니다.

Answer 1

단어와 그 짧은 버전 또는 긴 버전의 그래프를 만듭니다. 질문 (hat, chat, chats, rat, tat, tats, chatats)에서 단어 목록을 그은 다음과 같습니다

      chatats 
hat ─── chat ─── chats 
rat 
tat ─── tats 

, 모든 단어 즉, 뒤로 그래프를 빌드 선행 또는 후행 문자 중 하나를 제거하여이 개 짧은 단어를 찾습니다.

빠른 검색을 위해 그래프 노드에 Map 개의 단어를 작성하십시오.

이제 그래프에서 가장 긴 체인을 찾습니다.