串联排序数组中的字符串

Question

 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)，但不确定最坏的情况...也许O(n^2)一次只能匹配一个字母。

谁能给我更多的点子吗？

Answer 1

基本上，你提出的方法是一个递归搜索和回溯。它应该能正常工作，但应该存在能使你的算法在指数时间内运行的输入。

也许令人惊讶的是，使用正则表达式可以在线性时间内解决您的问题。在您的示例中，我们将测试正则表达式/(appleapplesbananaapleorangebananapearapples)*/是否与密钥匹配。

在自动机理论中研究了字符串与正则表达式的匹配问题，该问题可以用线性时间内的非确定性有限自动机来解决。