I have 2 sets of string arrays, say for example
array 1 -> "str1", "str2", "str3", "str12", "str13",....
array 2 -> "s", "t"
I am trying to do a "like search" of 2 on 1. This means that for every element in the array #2, I would find all matching strings from array #1. I end up writing 2 for loops as shown below
for (i from 0 to length of array 1) {
for (j from 0 to length of array 2) {
//check if ith element of array 1 contains jth element of array 2
}
}
If my array 1 and array 2 are really large arrays, then i end up doing a lot of looping. Can this be optimized?
I can't think of how to optimise your searches; you have got two parallel linear searches, no three parallel linear searches, if I have understood the question correctly:
Through the individual Strings of array 1.
Through the individual Strings of array 2.
Through the length of the current String to see whether part of it matches.
So you are stuck with cubic complexity.
It is worthwhile seeing whether it is possible to make one of the arrays into a regular expression, then iterating through the other array looking for matches, but I don't know whether that is any faster.
There is one way, as I think... but could involve a bit of preparation work on those arrays before the search operation.
step1: sort both the arrays [ascending or descending, but make sure both of the arrays are in the same order].
step2: start searching in order, and break the moment if an element in array2 is not found in array1.
As I mentioned, there is an added overhead of sorting the arrays before the operation, but if you can handle that, then this could optimize your search.
0
