查找包含子字符串的 Arraylist 的所有字符串的有效方法 [英] Efficient way of finding all strings of an Arraylist, which contains a substring

问题描述

我有一个字符串，比如 a="1.1" 和一个数组列表，比如 list，它有字符串:"1.1.1.1", "1.1.2.4","1.2,1.3","1.5.1.1"

现在，我想从这个数组列表中获取字符串，它的开头包含字符串 a="1.1"，这意味着 a 是这些字符串的子字符串，需要从头开始匹配.

因此，对于这种情况，答案将是 1.1.1.1 和 1.1.2.4 但不是 1.5.1.1 因为这里 1.1 不是一开始.

我知道如何实现这一点，但我认为我的解决方案不够高效，对于大型数组列表，需要更多的处理时间.

我的方法:为 arraylist 和每个字符串运行 for 循环，从开头用 a 的长度裁剪字符串，并检查裁剪后的字符串是否与 a 相等.

但是如果我想为一个大型数组列表的几个字符串重复这个，我认为这不是一个好的解决方案.

有什么想法吗?我将非常感谢您的帮助.

解决方案

嘿，你想要一些优化的解决方案，所以你可以试试这个:

<块引用>

1. 在Collections.sort(list);
的帮助下对列表进行排序
2. 在二进制搜索的帮助下找到第一个匹配的字符串，并用找到的前缀标记该字符串.
3. 现在如果下一个字符串不匹配这个前缀，这意味着列表的下一个字符串将匹配这个前缀，因为我们已经对集合进行了排序

试试这个代码:

包测试；导入 java.util.ArrayList;导入 java.util.Collections;导入 java.util.List;公共课 T {静态整数计数=0；公共静态无效主(字符串 [] args){列表<字符串>list = new ArrayList();//仅出于测试目的，我正在制作此列表并放置此数据for (int i = 101; i <501; i++) {list.add(i + "");}布尔匹配后缀 = 假；字符串前缀 = "30";Collections.sort(list);int startFrom = T.binarySearchOverList(list, prefix);if (startFrom == -1) {System.out.println("没有找到数据");} 别的 {for (int i = startFrom;; i++) {字符串 s = list.get(i);如果(s.startsWith(前缀)){//在这里你会得到匹配的字符串System.out.println(s);匹配后缀 = 真；} 别的 {如果(匹配后缀){休息;}}}}}public static int binarySerchOverList(List input, String prefix) {计数++；System.out.println("迭代次数为"+count);int size = input.size();int 中点 = 大小/2;int startPoint = 0;String stringToTest = input.get(midpoint);如果(stringToTest.startsWith(前缀)){起点 = 中点 - 1;而(真){if (!input.get(startPoint).startsWith(prefix)) {起点++；休息;}如果(起点== 0){休息;}起点 - ;}返回起点；}如果(stringToTest.compareTo(前缀)> 0){列表<字符串>sublist = input.subList(0, 中点);返回 binarySearchOverList(sublist, prefix);}如果 (stringToTest.compareTo(prefix) <0) {如果 (input.get(input.size() - 1).compareTo(prefix) <0) {返回-1；}列表<字符串>sublist = input.subList(midpoint, input.size());返回 binarySearchOverList(sublist, prefix);}返回0；}}

对代码有疑问可以问我

I have a string, say a="1.1" and an arraylist, say list, which has the strings: "1.1.1.1", "1.1.2.4","1.2,1.3","1.5.1.1"

Now, I want to get the strings from this arraylist, which contains the string a="1.1" at the beginning, that means a is a substring of those string and need to match from beginning.

So, for this case, answer will be 1.1.1.1 and 1.1.2.4 but not 1.5.1.1 as here 1.1 is not at the beginning.

I know, how to achieve this but I think my solution is not efficient enough and for large arraylist, it will take more processing time.

My approach: Run a for loop for the arraylist and for each string, crop the string from the beginning with the lenth of a and check if cropped string is equal with a.

But if I want to repeat this for several strings for a large arraylist, I think it is not a good solution.

Any idea? I will highly appreciate your help.

解决方案

Hey as you want some optimized solution so you can try this :

1. sort the list with help of Collections.sort(list);
2. find for first matching string with help of binary search and make flag that string with this prefix found.
3. now if next string doesnot match this prefix that means no next string of list will match this prefix as we have sorted the collection

Try this code :

package test;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class T { 
    static int count=0;     
    public static void main(String[] args) {    
        List<String> list = new ArrayList<String>();

       // for testing purpose only i am making this list and putting this data
        for (int i = 101; i < 501; i++) {
            list.add(i + "");
        }
        boolean matchedSuffix = false;
        String prefix = "30";

        Collections.sort(list);

        int startFrom = T.binarySerchOverList(list, prefix);

        if (startFrom == -1) {
            System.out.println("no data found");
        } else {
                for (int i = startFrom;; i++) {
                String s = list.get(i);
                if (s.startsWith(prefix)) {                     
                    //here you will get matching strings                    
                    System.out.println(s);
                    matchedSuffix = true;
                } else {
                    if (matchedSuffix) {
                        break;
                    }
                }

            }
        }    
    }

    public static int binarySerchOverList(List<String> input, String prefix) {    
        count++;
        System.out.println( "iteration count is "+count);       
        int size = input.size();
        int midpoint = size / 2;
        int startPoint = 0;

        String stringToTest = input.get(midpoint);
        if (stringToTest.startsWith(prefix)) {
            startPoint = midpoint - 1;
            while (true) {

                if (!input.get(startPoint).startsWith(prefix)) {
                    startPoint++;
                    break;
                }
                if (startPoint == 0) {
                    break;
                }   
                startPoint--;
            }   
            return startPoint;
        }

        if (stringToTest.compareTo(prefix) > 0) {
            List<String> sublist = input.subList(0, midpoint);
            return binarySerchOverList(sublist, prefix);
        }

        if (stringToTest.compareTo(prefix) < 0) {    
            if (input.get(input.size() - 1).compareTo(prefix) < 0) {
                return -1;
            }
            List<String> sublist = input.subList(midpoint, input.size());
            return binarySerchOverList(sublist, prefix);
        }    
        return 0;    
    }    
}

Ask me if you have doubt in code

这篇关于查找包含子字符串的 Arraylist 的所有字符串的有效方法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！