Find a complex element in a set of elements

I have a function that allows me to find a match between an incomplete element and at least one element in a set. An example of an incomplete element is 22.2.X.13, in which there is an item (defined with X) that could assume any value.

The goal of this function is to find at least one element in a set of elements that has 22 in the first position, 2 on the second, and 13 on the fourth.

For example, if we consider the set:

{
	20.8.31.13,
	32.3.29.13, 
	24.2.12.13, 
	19.2.37.13, 
	22.2.22.13, 
	27.17.22.13, 
	26.22.32.13, 
	22.3.22.13, 
	20.19.12.13, 
	17.4.37.13, 
	31.8.34.13
} 

The output of the function return True since there are elements 22.2.22.13 which correspond to 22.2.X.13.

My function compares each pair of elements like strings and each item of the elements as an integer:

public boolean containsElement(String element) {
	StringTokenizer strow = null, st = null;
	boolean check = true;
	String nextrow = "", next = "";
	
	for(String row : setOfElements) {
		strow = new StringTokenizer(row, ".");
		st = new StringTokenizer(element, ".");
		
		check = true;
		while(st.hasMoreTokens()) {
			next = st.nextToken();
			if(!strow.hasMoreTokens()) {
				break;
			}
			nextrow = strow.nextToken();
			if(next.compareTo("X") != 0) {
				int x = Integer.parseInt(next);
				int y = Integer.parseInt(nextrow);
				if(x != y) {
					check = false;
					break;
				}
			}
		}
		if(check) return true;
	}
	return false;

However, it is an expensive operation, particularly if the size of the string increases. Can you suggest to me another strategy or data structure to quickly perform this operation?

My solution is closely related to strings. However, we can consider other types for elements (e.g. array, list, tree node, etc)

Thanks to all for your answers. I have tried almost all the functions, and the bench:

myFunction: 0ms
hasMatch: 2ms
Stream API: 5ms
isIPMatch; 2ms

I think that the main problem of the regular expression is the time to create the pattern and match the strings.

You want to use Regex which is made exactly for tasks like this. Check out the demo.

22\.2\.\d+\.13

Java 8 and higher

You can use Stream API as of Java 8 to find at least one matching the Regex using Pattern and Matcher classes:

Set<String> set = ... // the set of Strings (can be any collection)

Pattern pattern = Pattern.compile("22\\.2\\.\\d+\\.13"); // compiled Pattern
boolean matches = set.stream()                           // Stream<String>
                     .map(pattern::matcher)              // Stream<Matcher>
                     .anyMatch(Matcher::matches);        // true if at least one matches

Java 7 and lower

The way is equal to Stream API: a short-circuit for-each loop with a break statement in case the match is found.

boolean matches = false;
        
Pattern pattern = Pattern.compile("22\\.2\\.\\d+\\.13");
for (String str: set) {
    Matcher matcher = pattern.matcher(str);
    if (matcher.matches()) {
        matches = true;
        break;
    }
}

You can solve this by approaching the problem in a regex-based manner, as suggested by Nikolas Charalambidis (+1), or you can do it differently. To avoid being redundant with another answer, I will focus on an alternative approach here, using the split method.

public boolean isIPMatch(String pattern[], String input[]) {
    if ((pattern == null) || (input == null) || (pattern.length <> input.length)) return false; //edge cases
    for (int index = 0; index < pattern.length; index++) {
        if ((!pattern[index].equals("X")) && (!pattern[index].equals(input[index]))) return false; //difference
    }
    return true; //everything matched
}

And you can call the method above in your loop, after converting the items to compare to String arrays via split.

For strings, regular expressions solve the task a lot better:

private boolean hasMatch(String[] haystack, String partial) {
    String patternString = partial.replace("X", "[0-9]+").replace(".", "\\.");
    // "22.2.X.13" becomes "22\\.2\\.[0-9]+\\.13" 
    Pattern p = Pattern.compile(patternString);
    for (String s : haystack) {
        if (p.matcher(s).matches()) return true;
    }
    return false;
}

For other types of objects, it depends on their structure.

• If there is some kind of order, you could consider making your elements implement Comparable - and then you can place them into a TreeSet (or as keys in a TreeMap), which will always be kept sorted. This way, you can compare only against the elements that can match: mySortedSet.subSet(fromElement, toElement) returns only the elements between those two.
• If there is no order, you will simply have to compare all elements against your "pattern".

Note that strings are comparable, but their default sorting order ignores the special semantics of your .-separators. So, with some care you can implement a treeset-based approach to make the search better-than-linear.

Other answers have already discussed using a regular expression by converting e.g. 22.2.X.13 to 22\.2\.\d+\.13 (don't forget to also escape the . or they mean "anything"). But while this will definitely be simpler and probably also a good bit faster, it does not lower the overall complexity. You still have to check each element in the set.

Instead, you might try to convert your set of IPs to a nested Map in this form:

{20: {8: {31: {13: null}}, 19: {12: {13: null}}}, 22: {2: {...}, 3: {...}}, ...}

(Of course, you should create this structure just once, and not for each search query.)

You can then write a recursive function match that works roughly as follows (pseudocode):

boolean match(ip: String, map: Map<String, Map<...>>) {
    if (ip.empty) return true // done
    first, rest = ip.splitfirst
    if (first == "X") {
        return map.values().any(submap -> match(rest, submap))
    } else {
        return first in map && match(rest, map[first])
    }
}

This should reduce the complexity from O(n) to O(log n); more than that the more often you have to branch out, but at most O(n) for X.X.X.123 (X.X.X.X is trivial again). For small sets, a regular expression might still be faster, as it has less overhead, but for larger sets, this should be faster.