查找前綴存在於單詞列表中

Question

現在，我有一種方法應該使用二進制搜索來查找前綴是否在列表中。

例如，用戶輸入「ca」，如果字典中包含「cat」，則該方法應該返回true。

這是我的方法，沿着它是一個輔助方法。我現在遇到的問題是，當我調用遞歸方法並且前綴大於字典中的單詞時，由於substring（）方法，我將得到一個索引超出界限的錯誤。

我使用此方法與遞歸函數結合起來，以查找字符串的所有排列。 （generateWords（）方法）。

如何修改此函數以檢查前綴是否在單詞列表中，因爲單詞列表中有不同長度的單詞？

public boolean findPrefix(String Prefix){ 
     return findBinaryPrefix(listOfWords, Prefix,0, listOfWords.size()-1, 0); 
    } 

    /** 
    * Helper function for findPrefix. 
    * @param list arraylist 
    * @param prefix prefix you want to find 
    * @param low lowest index 
    * @param high highest index of the array. 
    * @return returns true if prefix is in the dictionary, else false. 
    */ 
    private boolean findBinaryPrefix(ArrayList<String> list, String prefix, int low, int high, int prefixLength){ 
     int charCounter = prefixLength; 

     if(low>high){ 
      return false; 
     } 
     int mid = (low+high)/2; 
     if(list.get(mid).substring(0, charCounter).equals(prefix.substring(0, charCounter))){ 
      //If the word is equal, then that's the base case. 
      return true; 
     } 

     else if (list.get(mid).substring(0, charCounter).compareTo(prefix.substring(0, charCounter)) < 0){ 
      return findBinaryPrefix(list, prefix, mid+1, high, charCounter); 
     } 
     else 
      return findBinaryPrefix(list, prefix, low, mid-1, charCounter); 
    } 


private ArrayList<String> generateWords(Dictionary dict,String prefix, String seq){ 


     if(seq.length() == 0){ 
      if(dict.findWord(prefix)){ 
       permList.add(prefix); 
      } 

     } 
     else{ 
      for(int i = 0;i<seq.length(); i++){ 
       if(!dict.findPrefix(prefix)){break;} 
       //if prefix is not even in dictionary, don't bother generating. 

       //generate permutations when the character is in a different position with each iteration of the loop. 
       generateWords(dict, prefix + seq.charAt(i) ,seq.substring(0,i) + seq.substring(i+1, seq.length())); 
      } 
     } 

     return permList; 
    } 

Answer 1

添加

if(list.get(mid).length() < charCounter) { 
//do something 
}