0

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

给定一个键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) 一次只能匹配一个字母。

谁能给我更多的想法？

4

2 回答 2

2

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

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

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

于 2013-05-16T00:21:43.390 回答
0

我们可以有一个插入单词列表中所有单词的 Trie 吗？

  • 我们可以获取整个关键字，一次一个字母，直到我们到达树的叶子。
  • 在到达 LEAF 时，我们找到了关键词的一部分。
  • 继续 TRIE 搜索关键字中所有剩余的字母/子词。
  • 如果我们在 TRIE 中同时到达关键字 && 到达 LEAF 的末尾，那么我们将使用 TRIE 中的单词组合进行匹配。
于 2013-05-16T05:28:07.320 回答