java - ソートされた配列から文字列を連結します

Question

こんにちは、私は面接の練習をしています。この問題に対するより良い解決策があるかどうか知りたいです。

キーString key="apple"と並べ替えられた文字列の配列を指定すると、String[] words ={apple, apples, bananaaple, orangebanana, pearapples}

できない場合はtrue、単語リストから単語を使用してキー文字列を取得するために連結できるときに戻る関数を作成します。false

私の考えは、キー文字列の 1 文字から始めて、ワールド リストからバイナリ検索を行い、存在する場合は残りの文字列を見つけることです。そうでない場合は、もう 1 文字増やして、同じことを行います。

私のコード:

 public static void main(String[] args){
        String[] words = {"apple", "apples", "bananaaple", "orangebanana", "pearapples"};

        String key = "apple";

        System.out.println(expanding(words,key));
    }


    public static boolean expanding(String[] words, String key){
        if(key.length()<1){
            return false;
        }

        for(int i=1; i<=key.length(); i++){
            String sub = key.substring(0, i);
            boolean found =search(words,sub,0,words.length-1);
            if(found){ //get next piece
                String theSubString =key.substring(i, key.length());
                if(theSubString.compareToIgnoreCase("")==0){
                    return found;
                }
                boolean re = expanding(words,theSubString );
                if(re)
                    return true;
            }
        }
        return false;
    }

    public static boolean search(String[] list, String key, int min, int max){
        if(min>max){
            return false;
        }
            int mid = (min+max)/2;
            if(list[mid].compareToIgnoreCase(key)==0){
                return true;
            }else if(list[mid].compareToIgnoreCase(key)<0){
                return search(list,key,mid+1,max);
            }else{
                return search(list,key,min,mid-1);
            }

    }

私の意見では、最良のケースは O(log n) である必要がありますが、最悪のケースはわかりません... 一度に 1 文字しか一致しない場合はおそらく O(n^2) です。

誰か私にもっとアイデアを教えてもらえますか？