자동 완성 사용 시도 횟수

Question

import java.util.ArrayList; 


public class AutoComplete { 
    boolean newWord = false; 
    ArrayList<String> all = new ArrayList<String>(); 

    static TrieNode root = new TrieNode('!', false, null); 

    void add(String s){ 
     TrieNode temp = root; 
//  TrieNode parent = root; 

     for(int i=0; i < s.length(); i++){ 
      int t = s.charAt(i); 
      t = t - 97; 
      while((temp.links[t]) != null && i < s.length()-1){ 

       temp = temp.links[t]; 
       t = s.charAt(++i); 
       t = t - 97; 

//    parent = temp; 
      } 
      if(i != s.length()-1){ 
       temp.links[t] = new TrieNode((char)(97+t), false, null); 
//    parent = temp.links[t]; 
      } 
      else{ 
       temp.links[t] = new TrieNode((char) (97+t), true, null); 
//    parent = temp.links[t];   
      } 
      temp = temp.links[t]; 
     } 
    } 

    void readTree(String find){ 
     int len = find.length(); 
     int i = 0; 
     TrieNode temp = root; 
     String match = ""; 
     while(i != len){ 
      int t = find.charAt(i); 
      t = t - 97; 
      temp = temp.links[t]; 
      if(temp == null) 
       break; 
      match = match + temp.letter; 
      i++; 
     } 
     if(match.length() > 0) 
      match = match.substring(0,match.length()-1); 
     printAll(temp, match); 
    } 

    void printAll(TrieNode t, String parent){ 
     if(t== null) 
      return; 
     parent = parent + t.letter; 
     if(t.fullWord){ 
      System.out.println(parent); 
     } 
     for(int i = 0; i < 26; i++){ 
      printAll(t.links[i], parent); 
     } 
    } 

    public static void main(String[] args) { 
     // TODO Auto-generated method stub 
     AutoComplete a = new AutoComplete(); 

     a.add("tea"); 
     a.add("team"); 
     a.add("teach"); 
     a.add("teacher"); 
     a.readTree("t"); 
    } 

} 

트라이의 요소가 나는 순서대로 요소를 추가하면 더 높은 길이

에 낮은 길이에서 추가 될 때 내가 시도를 사용하여 자동 완성을 구현하기 위해 노력하고

, 그것은 잘 작동

a.add("tea"); 
a.add("team"); 
a.add("teach"); 
a.add("teacher"); 

나는 a.readTree("t");

tea 
teach 
teacher 
team 

에 대한하지만 경우 출력을 다음 얻을 내가 a.readTree("t");

tea 

최종 작업 솔루션

public class AutoComplete { 
    void add(String s, TrieNode root){ 
     //To keep the root node intact 
     TrieNode temp = root; 

     //Iterate through each char in string s 
     for(int i=0; i < s.length(); i++){ 
      //each character in string 
      int t = s.charAt(i); 
      //its corresponding value in array links 
      t = t - 'a'; 
      //if some part of string is already present in array then just loop through it except th 
      while((temp.links[t]) != null && i < s.length()-1){ 
       //increment i since first char is present 
       i = i +1; 
       //increment in trie 
       temp = temp.links[t]; 
       //go to next char in string and 
       //go to that char location in array 
       t = s.charAt(i)- 'a'; 
      } 
      //Add only till before the last character 
      if(i < s.length()-1){ 
       temp.links[t] = new TrieNode((char)('a'+t), false); 
      } 
      //for last character of string 
      else{ 
       // if last character is not present 
       if(temp.links[t] == null){ 
        temp.links[t] = new TrieNode((char) ('a'+t), true);     
       } 
       // if last character already exist 
       else{ 
        temp.links[t].fullWord = true; 
       } 
      } 
      //increment the trie 
      temp = temp.links[t]; 
     } 
    } 
    void readTree(String find, TrieNode root){ 
     //get length in len 
     int len = find.length(); 
     int i = 0; 
     TrieNode temp = root; 
     //initialize string to store the result 
     String match = ""; 
     while(i < len){ 
      //get first char of search string 
      int t = find.charAt(i) - 'a'; 
      //go to its array location 
      temp = temp.links[t]; 
      //location is null then break else continue 
      if(temp == null) 
       break; 
      //keep appending the found char and increment the index 
      match = match + temp.letter; 
      i++; 
     } 
     //if suggestions exist 
     if(match.length() > 0) 
      //pass the match string except for the last element 
      match = match.substring(0,match.length()-1); 
     printAll(temp, match); 
    } 

    void printAll(TrieNode t, String parent){ 
     if(t== null) 
      return; 
     parent = parent + t.letter; 
     if(t.fullWord){ 
      System.out.println(parent); 
     } 
     for(int i = 0; i < 26; i++){ 
      printAll(t.links[i], parent); 
     } 
    } 

    public static void main(String[] args) { 
     // TODO Auto-generated method stub 
     TrieNode root = new TrieNode('!', false); 
     AutoComplete a = new AutoComplete(); 

     a.add("tea", root); 
     a.add("team", root); 
     a.add("teach", root); 
     a.add("teacher", root); 
     a.readTree("t", root); 
    } 

} 

Answer 1

을위한 출력 다음 얻을

a.add("teacher"); 
a.add("teach"); 
a.add("team"); 
a.add("tea"); 

의 순서로 DD 요소는 문제는 여기에 있습니다 :

else{ //i == s.length - 1 
     temp.links[t] = new TrieNode((char) (97+t), true, null);  
    } 

추가 할 때 "차 ch "이면, 교사의 노드 'h'를 대체하는 char 'h'노드가 새로 추가됩니다. 당신은 이런 식으로 작성해야하십시오 Trie의 개념이 제대로 코드에서

else{ //i == s.length - 1 
     if(temp.links[t] == null) { 
      temp.links[t] = new TrieNode((char) (97+t), true, null);  
     } 
     else { 
      // change the leaf tag from false to true 
     } 
    } 

Answer 2

을 캡처 한 것 같다. for 및 while 루프의 가능한 모든 사례를 식별하는 것은 상당히 어려우며 여전히 읽을 수 있습니다. "제대로 실행하고 신속하게 만들 수 있습니다"방식으로 가능한 한 간단하게 첫 번째 구현을 유지해야합니다.

문자열을 Trie에 추가하는 순서가 쿼리 결과에 영향을 주면 코드가 분명히 이 아니며이 실행됩니다. 가능한 한 간단하게 유지하려면 새롭게 추가 된 문자열의 첫 번째 문자를 살펴보고 root에서 찾은 다음에 재귀를 사용하면됩니다. 이것은 런타임을 날려 버릴 수 있지만 세 번째 고려 사항입니다 (을 만든 후로 지정). TrieNode을 어떻게 구현할 것인지 알려주지 않으면 답변을 너무 많이 변경합니다.