java - 从排序的数组中连接一个字符串

Question

你好，我正在为我的面试练习，我想知道这个问题是否有更好的解决方案:

给定一个键 String key="apple" 和一个排序的字符串数组，String[] words ={apple, apples, bananaaple, orangebanana, pearapples}

编写一个函数，当您可以使用单词列表中的单词连接以获取关键字符串时返回 true，如果不能则返回 false。

我的想法是从关键字符串中的一个字母开始，然后从世界列表中进行二进制搜索，如果存在，则找到字符串的其余部分；如果不是，再增加一个字母，照样做。

我的代码:

 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

基本上，您提出的方法是带回溯的递归搜索。它应该可以正常工作，但应该存在可以使您的算法以指数时间运行的输入。

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

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