다른 문자열의 접두어 인 문자열 찾기

Question

이것은 인터뷰 질문입니다. 주어진 수의 문자열은 다른 문자열의 접두사 인 문자열을 찾습니다. 예를 들어, strings = {"a", "aa", "ab", abb"}으로 주어진 결과는 {"a", "ab"}입니다.

가장 간단한 해결 방법은 첫 번째 문자열이 두 번째 문자열의 접두사 인 경우 문자열을 정렬하고 두 개의 연속 된 문자열 쌍을 확인하는 것입니다. 알고리즘의 실행 시간은 정렬 실행 시간입니다.

trie을 사용하는 다른 솔루션이 있으며 복잡도가 O(N)인데, 여기서 N은 문자열의 수입니다. 그런 알고리즘을 제안 해 주시겠습니까?

Answer 1

O(n*|S|) 내가 트리는에 관한 다음과 같은 생각을 가지고있다, 복잡도 O (N)는 : 당신은 빈 트리는 시작합니다. 단어 하나 하나를 가져 와서 단어를 Trie에 추가하십시오.

1. 무선은 이전에 추가 한 단어의 일부 접두어 : 당신이 단어를 추가 한 후 트리는에 (의이 단어 무선 부르 자), 고려해야 할 두 가지 경우가 있습니다. 단어 Wi를 추가하는 동안 Trie에 노드를 추가하지 않으면이 명령문은 true입니다. 이 경우 Wi는 접두어이며 우리 솔루션의 일부입니다.
2. 앞에 추가 된 단어 중 일부는 Wi의 접두사입니다. 이전에 추가 한 단어의 끝을 나타내는 노드를 통과 한 경우 해당 문이 true입니다 (해당 단어 Wj를 보정하자). 이 경우 Wj는 Wi의 접두어이며 우리의 솔루션의 일부입니다. 자세한 내용은에서

(의사) :

for word in words 
    add word to trie 
    if size of trie did not change then // first case 
     add word to result 
    if ending nodes found while adding word // second case 
     add words defined by those nodes to result 
return result 

트리는 새로운 단어를 추가 : 새 단어를 추가하는 동안 당신이 어떤 노드를 통과하면

node = trie.root(); 
for letter in word 
    if node.hasChild(letter) == false then // if letter doesnt exist, add it 
     node.addChild(letter) 
    if letter is last_letter_of_word then // if last letter of word, store that info 
     node.setIsLastLetterOf(word) 
    node = node.getChild(letter) // move 

, 당신은 또한 확인하실 수 있습니다 다른 단어의 마지막 글자를 나타냅니다. 내가 설명한 알고리즘의 복잡도는 O (N)입니다. 또 다른 중요한 점은 단어 Wi가 다른 단어 앞에 몇 번이나 붙는 지 알 수 있기 때문에 유용 할 수 있습니다. 위한

예 {AAB, AABA, AA는} 그린 노드 1 레드 노드는 대소 2 각 열 (트라이)로 감지 노드에있는 경우로서 검출 노드이다 한 단계이다. 처음에는 trie가 비어 있습니다. 검은 색 화살표는 해당 단계에서 우리가 방문한 (추가 된) 노드를 나타냅니다. 일부 단어의 마지막 문자를 나타내는 노드는 해당 단어가 괄호 안에 쓰여 있습니다. 1 단계에서

은

1. 

   우리는 단어 AAB를 추가합니다.
2. 2 단계에서 단어 aaba를 추가하고 사례 2 (단어 aab)를 인식하고 단어 aab를 결과에 추가합니다.
3. 3 단계에서 단어 aa를 추가하고 사례 1을 인식 한 다음 단어 aa를 결과에 추가합니다.

결국 우리는 결과 = {aab, aa}가 맞습니다.

Answer 2

원래 대답은 다음과 같습니다. 문자열은 ab (오독)입니다.

트라이를 사용하면 첫 번째 반복에서 모든 문자열을 추가하고 두 번째 반복에서는 각 단어를 읽기 시작하여 w이되도록 할 수 있습니다. 읽은 단어를 찾았지만 문자열 종료 자 (보통 $)에 도달하지 않은 경우 trie의 노드 v에 도달합니다.
v에서 DFS을 수행하면 w의 접두사 인 모든 문자열을 가져올 수 있습니다.

는

높은 수준의 의사 코드 :

t <- new trie 
for each word w: 
    t.add(w) 
for each word w: 
    node <- t.getLastNode(w) 
    if node.val != $ 
    collection<- DFS(node) (excluding w itself) 
    w is a prefix of each word in collection 

참고 :을 최적화하기 위해, 당신은 몇 가지 추가 작업을 할 필요가 있습니다 a이 b의 접두사 인 경우, 그리고 b 다음, ac의 접두어입니다 접두사가 c 인 경우 DFS를 수행 할 때 이미 검색 한 노드에 도달하면 문자열을 현재 접두어에 추가하기 만하면됩니다.
그래도 이차 숫자의 가능성 ("a", "aa", "aaa", ....)이있을 수 있기 때문에 모두 얻기에는 2 차 시간이 필요합니다.

---

원래 답 : a 경우 발견이 문자열 b의입니다 :

제안 된 솔루션은 사절 복잡성에서 실행, 당신은 당신 O(n* (n-1) * |S|)주고, 각 두 쌍 확인해야합니다.

첫 번째 반복에서는 문자열에서 suffix tree을 만들고 두 번째 반복 검사에서는 각 문자열이 다른 문자열의 간단한 항목이 아닌지 확인하십시오.
이 솔루션은