2

I have 2 strings of pattern a.{var1}.{var2} and b.{var1}.{var2}.

Two Strings are matching if var1 in first string is same as var1 in second string, as well as var2 in first string is same as var2 in second string.

The variables can be any order like a.{var1}.{var2} and b.{var2}.{var1}.

How do I match the two strings efficiently?

Example 1:

String pattern1 = "1.{var1}";
String pattern2 = "2.{var1}";

//Match True = (1.111,2.111)
//Match False = (1.121,2.111)

Example 2:

String pattern1 = "1.{var1}.{var2}";
String pattern2 = "2.{var1}.{var2}";

//Match True = (1.11.22,2.11.22)
//Match False = (1.11.22,2.111.22)

Example 3:

String pattern1 = "1.{var1}.{var2}";
String pattern2 = "2.{var2}.{var1}";

//Match True = (1.22.11,2.11.22)
//Match False = (1.11.22,2.111.22)

So whats the best way to match these 2 strings?

I want to match these 2 strings to find if they are related with the pattern mentioned.
Extending this problem to a set of strings i.e Set A strings has to be matched with strings in Set B. Finally pairs of strings have to be formed which satisfy this matching algorithm. The pattern will remain the same when matching for all strings in Set A to Set B.

Improve this question
6
  • You might want to tokenize the strings and compare individual tokens. Commented Apr 24, 2018 at 16:00
  • This looks convoluted, almost like you are trying to build your own regex engine of some sort. Maybe explain more the logic of why matches are happening. Commented Apr 24, 2018 at 16:01
  • Are you trying to compare the numbers that are separated by decimals? As in (5.9278.30) 5 would be one group, 9278 would be another and 30 would the last group? Commented Apr 24, 2018 at 16:03
  • Which part are you having trouble with? Commented Apr 25, 2018 at 3:37
  • I want to optimize it for matching one list of strings with another in least complexity. Commented Apr 25, 2018 at 4:21

6 Answers 6

Reset to default
2

This might not be the most efficient way of doing this, but it does give you the expected output.

01/05: Code updated after an error pointed out by Ole in the comments::

private boolean compareStr(String a, String b) {
    ArrayList<String> aList = new 
    ArrayList<String>(Arrays.asList(a.split("\\.")));
    ArrayList<String> bList = new ArrayList<String>(Arrays.asList(b.split("\\.")));
    bList.remove(0);
    aList.remove(0);

    if(aList.size() != bList.size())
            return false;

    boolean aMatchFlag = false;
    for(int i=0; i< aList.size(); i++){
        if (!bList.contains(aList.get(i))) {
            return false;
        }
    }
    aMatchFlag = true;
    System.out.println("All elements of A are present in B");
    boolean bMatchFlag = false;
    for(int i=0; i< bList.size(); i++){
        if (!aList.contains(bList.get(i))) {
            return false;
        }
    }
    bMatchFlag = true;
    System.out.println("All elements of B are present in A");

    if(aMatchFlag && bMatchFlag)
            return true;
    else
            return false;
}

For those also looking for the performance of the code

Input:1.11.11, 2.11.11.11
Compilation time: 1.45 sec, absolute running time: 0.24 sec, cpu time: 0.26 sec, memory peak: 18 Mb, absolute service time: 1,7 sec

Input:1.11.11, 2.11.22
Compilation time: 1.25 sec, absolute running time: 0.24 sec, cpu time: 0.23 sec, memory peak: 18 Mb, absolute service time: 1,49 sec

Input:1.11.2, 2.11.22
Compilation time: 1.34 sec, absolute running time: 0.24 sec, cpu time: 0.24 sec, memory peak: 18 Mb, absolute service time: 1,58 sec


Input:1.11.2, 2.11.111
Compilation time: 1.65 sec, absolute running time: 0.28 sec, cpu time: 0.32 sec, memory peak: 18 Mb, absolute service time: 1,94 sec
Improve this answer
Sign up to request clarification or add additional context in comments.

6 Comments

you need to check strings if the first element in both is matching the pattern .. I'm talking about "1" and "2" in the strings .
I think you’re helping too much. The asker will learn much more from being guided in the right direction and having to write the actual code himself/herself. Your code is not correct, however. It will say that 1.11.11 and 2.11.22 match and that 1.2.3 and 2.111.3 match.
@Mohammad sorry I didn't get you
@OleV.V. thanks for pointing out that, i have made the change to handle the scenario which you have mentioned
@OleV.V. it would have, but try it now
|
1

You can use following String class methods:

boolean regionMatches(int toffset, String other, int ooffset, int len)

Tests whether the specified region of this string matches the specified region of the String argument. Region is of length len and begins at the index toffset for this string and ooffset for the other string.

For ignoring case:

boolean regionMatches(boolean ignoreCase, int toffset, String other, int ooffset, int len)

More information : https://docs.oracle.com/javase/tutorial/java/data/comparestrings.html

Or try to create a Regex pattern dynamically from one string and compare with other ...though not an efficient approach

Improve this answer

Comments

0

I suppose following:

string[] arr1 = pattern1.split
string[] arr2 = pattern2.split
int hash1 = arr1[0].hashCode() + arr1[1].hashCode();
int hash2 = arr2[0].hashCode() + arr2[1].hashCode();
if(hash1 = hash2)=> pattern1 == pattern2
Improve this answer

1 Comment

Will not always work. It says that 11.22 and 12.21 match, which they clearly don’t.
0

Remove the patterns from the String, extract the vars from the String by splitting around the dot (assuming your vars has no dots inside), put them in a Set (Sets don't retain the order and hence automatically solve the problem you have with ignoring the position), Check the equality of the Sets.

Running demo: https://ideone.com/5MwOHC

Example code: 

final static String pattern1head = "blablabla.";
final static String pattern2head = "yada yada.";

private static Set<String> extractVars(String v){
    if      (v.startsWith(pattern1head)) { v = v.replace(pattern1head,""); }
    else if (v.startsWith(pattern2head)) { v = v.replace(pattern2head,""); }
    else                                 { return null; }           

    return new HashSet<String>(Arrays.asList(v.split("\\.")));
}

private static void checkEquality(String v1, String v2) {
    System.out.println("\n"+v1+" == "+v2+" ? " + extractVars(v1).equals(extractVars(v2)));  
} 


public static void main (String[] args) throws java.lang.Exception {
    String v1 = "blablabla.123.456";
    String v2 = "yada yada.123.456";
    String v3 = "yada yada.456.123";
    String v4 = "yada yada.123.456789";

    checkEquality(v1,v2);
    checkEquality(v1,v3);
    checkEquality(v1,v4);
    checkEquality(v2,v3);
    checkEquality(v2,v4);
}

Output:

blablabla.123.456 == yada yada.123.456 ? true

blablabla.123.456 == yada yada.456.123 ? true

blablabla.123.456 == yada yada.123.456789 ? false

yada yada.123.456 == yada yada.456.123 ? true

yada yada.123.456 == yada yada.123.456789 ? false
Improve this answer

Comments

0

This can be done as follows:

  • While we check if the first string and the first pattern match, we extract a map of the values in the string corresponding to the placeholders (var1, var2, ...) in the pattern;
  • While we check if the second string and the second pattern match, we also check the second string against the values of the placeholders.

This is interesting, because the map placeholder - > value is computed once for a couple (first string, first pattern), and can be used to check every couple (second string, second pattern).

Translation in the code: create an object of type PatternMatcher from (first string, first pattern). This object will contain a map valueByPlaceHolder used to check other couples.

Here are the relevant parts of the code.

Check if string and pattern match + creation of the map:

private static Optional<Map<String, String>> extractValueByPlaceHolder(
        String[] sChunks, String[] patternChunks) {
    // string and pattern should have the same length
    if (sChunks.length != patternChunks.length)
        return Optional.empty();

    Map<String, String> valueByPlaceHolder = new HashMap<>(sChunks.length);
    for (int i = 0; i < patternChunks.length; i++) {
        String patternChunk = patternChunks[i];
        String sChunk = sChunks[i];
        if (isAPlaceHolder(patternChunk)) { // first char = {, last char = }
            valueByPlaceHolder.put(patternChunk, sChunk); // just get the value
        } else if (!patternChunk.equals(sChunk)) {
            // if it's not a placeholder, the chunks should be the same in the string
            // and the pattern
            return Optional.empty(); 
        }
    }
    return Optional.of(valueByPlaceHolder);
}

Check if other string and otherpattern match + comparison with first (string, pattern) couple:

public boolean check(String[] otherChunks, String[] otherPatternChunks) {
    // other string and other pattern should have the same length, other string and string too
    if (otherChunks.length != this.chunks_length || otherChunks.length != otherPatternChunks.length)
        return false;

    for (int i = 0; i < otherChunks.length; i++) {
        String otherPatternChunk = otherPatternChunks[i];
        String otherChunk = otherChunks[i];
        // get the value from the first string if a it's placeholder, else keep the pattern chunk 
        String expectedChunk = this.valueByPlaceHolder
                .getOrDefault(otherPatternChunk, otherPatternChunk);

        // the chunk is neither equal to the value of the placeholder, nor to the chunk of the pattern 
        if (!expectedChunk.equals(otherChunk))
                return false;
    }
    return true;
}
Improve this answer

Comments

0

Use String.split() and then String.equals() on the resulting array elements, handling your three cases separately.

After splitting, first check that both the resulting arrays have the same length (if not they don’t match). Also use String.equals() for checking that the first element is "1" and "2" if this is required. Then branch on whether the length is 2 or 3. If length is 2, check that the match is as in your example 1; again use String.equals() on the array elements. If length is 3, you need to check both orders of the variable parts in accordance with your two examples 2 and 3.

Remember that the argument to String.split() is a regular expression, and that the dot has a special meaning in regular expressions. So you need to use .split("\\."), not .split(".").

It should run pretty fast too. However, don’t start optimizing until you know you need better performance. Readability is king.

Edit: I present my own solution:

public static boolean match(String s1, String s2) {
    String[] a1 = s1.split("\\.", 4);
    String[] a2 = s2.split("\\.", 4);
    if (a1.length != a2.length) {
        return false;
    }
    if (a1[0].equals("1") && a2[0].equals("2")) {
        if (a1.length == 2) {
            return a1[1].equals(a2[1]);
        } else if (a1.length == 3) {
            return (a1[1].equals(a2[1]) && a1[2].equals(a2[2]))
                    || (a1[1].equals(a2[2]) && a1[2].equals(a2[1]));
        }
    }
    return false;
}

Trying it with the 6 examples from the question:

System.out.println("(1.111,2.111)      " + match("1.111", "2.111"));
System.out.println("(1.121,2.111)      " + match("1.121", "2.111"));
System.out.println("(1.11.22,2.11.22)  " + match("1.11.22", "2.11.22"));
System.out.println("(1.11.22,2.111.22) " + match("1.11.22", "2.111.22"));
System.out.println("(1.22.11,2.11.22)  " + match("1.22.11", "2.11.22"));
System.out.println("(1.11.22,2.111.22) " + match("1.11.22", "2.111.22"));

This prints:

(1.111,2.111)      true
(1.121,2.111)      false
(1.11.22,2.11.22)  true
(1.11.22,2.111.22) false
(1.22.11,2.11.22)  true
(1.11.22,2.111.22) false
Improve this answer

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.