查找包含子字符串的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"

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"

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

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.

因此，在这种情况下，答案将是1.1.1.1和1.1.2.4，但不是1.5.1.1，因为此处1.1并不是开头.

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.

我知道如何实现此目标，但是我认为我的解决方案效率不够高，对于大型arraylist，这将需要更多的处理时间.

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.

我的方法: 对arraylist运行一个for循环，然后为每个字符串从a的最短处开始裁剪该字符串，并检查裁剪后的字符串是否与a相等.

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. 在Collections.sort(list);
的帮助下对列表进行排序
2. 借助二进制搜索找到第一个匹配的字符串，并标记找到具有此前缀的字符串.
3. 现在下一个字符串是否不匹配此前缀，这意味着在我们对集合进行排序时，列表的下一个字符串都不匹配该前缀

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

尝试此代码:

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屋！