实现与字符串preFIX二进制搜索？ [英] implement binary search with string prefix?

问题描述

我如何能实现二进制搜索找到与通用阵列特定preFIX（在这种情况下将是一个字符串[]）的字符串。我试过的compareTo但不会帮助，因为我必须使用字符串preFIX。如字符串preFIX碧的法案，bilards ...等。

实现以下方法返回的所有字符串在按字母顺序排序数组与给定的pre网络x起动。例如，给定一个pre网络X璧，返回的字符串是克林顿，比尔·盖茨和比尔·乔伊。请注意，所有的字符串比较应区分大小写。在返回的列表中的字符串必须在它们出现在数组中的顺序。您的实施必须基于二进制搜索，并且必须在运行最坏的情况下为O（log的n + k）的时间，其中n是阵列的长度，k是匹配串的个数。假设数组有没有重复的条目。如果没有比赛，你既可以返回null或空数组列表。

您可以使用以下String方法（除了你可能还记得其他任何）：
布尔startsWith（String s）将
INT的compareTo（String s）将
INT与compareToIgnoreCase（String s）将
字符串与toLowerCase（String s）将
字符串与toUpperCase（String s）将
（至于ArrayList中，你只需要使用Add方法将项目添加到数组列表的末尾）。
您可以写信辅助方法（与全面实施）是必要的。你可能不叫你还没有实现自己的任何方法

 公共静态＆LT;吨延伸可比＆LT; T＆GT;＆GT; ArrayList的prefixMatch（T []列表中，字符串preFIX）{        ArrayList的＆LT; T＆GT;结果=新的ArrayList＆LT; T＆GT;（）;
        INT LO = 0;
        INT HI = List.length的数字 -  1;        而（LO＆LT; =喜）{            INT中旬=（喜+ LO）/ 2;            列表[MID] .startsWith（preFIX）？ 0：列表[MID] .compareTo（（T）preFIX））;
        }        返回null;
    }
 

解决方案

您可以使用自定义比较默认的二进制搜索你的基地，然后你自己的工作我们的产品系列。我认为正确的算法应该是：

1. 执行给定的阵列上二进制搜索。使用比较器，检查仅为preFIX。


2. 作为导致你会得到字符串的指数，与你的preFIX
启动

3. 走到左边找到相匹配preFIX第一个字符串，记住位置。


4. 步行到右边找到相匹配preFIX第一个字符串，记住位置。

从范围开始
5. 复制元素的范围从原来的数组结束。这将是你想要用preFIX匹配条件的所有元素的数组。

下面是Java实现。它工作在快乐的情况下反而会崩溃，如果（我离开那些检查出尽code看起来很简单）：

• 给定preFIX没有字符串在原数组存在


• 有字符串长度小于preFIX长度

此外，如果你需要二进制搜索实现，你可以检查 Arrays.binarySearch

来源

 公共类$ P $ {pfixMatch    公共静态无效的主要（字串[] args）{        最终的String [] prefixMathces = prefixMatch（新的String [] {ABC，ABCD，QWERTY，pre1，pre2，pre3 ，XYZ，呼噜栈}，pre）;        的for（int i = 0; I＆LT; prefixMathces.length;我++）
            的System.out.println（prefixMathces [I]）;
    }    公共静态的String [] prefixMatch（最终String []数组，最后弦乐preFIX）{        最后比较＆LT;串GT; preFIX_COMPARATOR =新的比较＆LT;串GT;（）{
            @覆盖
            公众诠释比较（字符串O1，O2的字符串）{
                返回o1.substring（0，prefix.length（））与compareToIgnoreCase（O2）。
            }
        };        最终诠释randomIndex = Arrays.binarySearch（数组，preFIX，preFIX_COMPARATOR）;        INT rangeStarts = randomIndex，rangeEnds = randomIndex;        而（rangeStarts -1个和放大器;＆安培;阵列[rangeStarts] .toLowerCase（）startsWith（prefix.toLowerCase（）））
            rangeStarts--;        而（rangeEnds＆LT; array.length＆放大器;＆安培;阵列[rangeEnds] .toLowerCase（）startsWith（prefix.toLowerCase（）））
            rangeEnds ++;        返回Arrays.copyOfRange（数组，rangeStarts + 1，rangeEnds）;
    }
}
 

How can I implement binary search to find a string with a particular prefix in generic array (which in this case will be a string[]). I tried compareTo but that wouldn't help because i have to use a string prefix. eg String prefix "Bi" bill, bilards ...etc..

Implement the following method to return all strings in an alphabetically sorted array that start with a given prefix. For instance, given a prefix "bi", the returned strings are "Bill Clinton", "Bill Gates", and "Bill Joy". Note that all string comparisons should be case INSENSITIVE. The strings in the returned list must be in the order in which they appear in the array. Your implementation must be based on binary search, and must run in worst case O(log n+k) time, where n is the length of the array, and k is the number of matching strings. Assume that the array has no duplicate entries. If there are no matches, you may either return null, or an empty array list.

You may use the following String methods (in addition to any others you may recall): boolean startsWith(String s) int compareTo(String s) int compareToIgnoreCase(String s) String toLowerCase(String s) String toUpperCase(String s) (As for ArrayList, you only need to use the add method to add an item to the end of the array list.) You may write helper methods (with full implementation) as necessary. You may not call any method that you have not implemented yourself

public static <T extends Comparable<T>> ArrayList prefixMatch(T[] list, String prefix) {

        ArrayList<T> result = new ArrayList<T>();
        int lo = 0;
        int hi = list.length - 1;

        while(lo <= hi) {

            int mid = (hi + lo) / 2;

            list[mid].startsWith(prefix) ? 0 : list[mid].compareTo((T) prefix));


        }   

        return null;
    }

解决方案

You can use default binary search with custom comparator as your base, and then work our range by your self. I think the right algorithm would be:

1. Perform binary search on given array. Use comparator which checks only for prefix.
2. As result you'll get index of string which starts with your prefix
3. Walk to the left to find first string which matches prefix, remember position.
4. Walk to the right to find first string which matches prefix, remember position.
5. Copy elements from range start to range end from original array. That will be your desired array of all elements with prefix match condition.

Below is implementation in java. It works in happy case scenario but will crash if(I left those checks out to make code look simple):

• No strings with given prefix exist in original array
• There are string with length less then prefix length

Also if you need binary search implementation you could check source of Arrays.binarySearch

public class PrefixMatch {

    public static void main(String[] args) {

        final String[] prefixMathces = prefixMatch(new String[] { "Abc", "Abcd", "Qwerty", "Pre1", "Pre2", "Pre3", "Xyz", "Zzz" }, "pre");

        for (int i = 0; i < prefixMathces.length; i++)
            System.out.println(prefixMathces[i]);
    }

    public static String[] prefixMatch(final String[] array, final String prefix) {

        final Comparator<String> PREFIX_COMPARATOR = new Comparator<String>() {
            @Override
            public int compare(String o1, String o2) {
                return o1.substring(0, prefix.length()).compareToIgnoreCase(o2);
            }
        };

        final int randomIndex = Arrays.binarySearch(array, prefix, PREFIX_COMPARATOR);

        int rangeStarts = randomIndex, rangeEnds = randomIndex;

        while (rangeStarts > -1 && array[rangeStarts].toLowerCase().startsWith(prefix.toLowerCase()))
            rangeStarts--;

        while (rangeEnds < array.length && array[rangeEnds].toLowerCase().startsWith(prefix.toLowerCase()))
            rangeEnds++;

        return Arrays.copyOfRange(array, rangeStarts + 1, rangeEnds);
    }
}

这篇关于实现与字符串preFIX二进制搜索？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！