Algorithm for text similarity search

Question

say I have String x= "algorithm" , and Stringy= "mgth"

String x contains all the letters in String y, I can split String y into a list of letters, and loop through this list to see if String x contains the letter y[index] ,, but I wonder If there's a more efficient way

Edit:

in kotlin there's a simple intersect function,, for example:

val x="algorithm".toList()
val y="mgth".toList()
val interesct=x.intersect(y) //returns a Set of matching chars

if (y.size == interesct.size){
    println("match")
}

uptoyou · Accepted Answer · 2019-07-14 19:47:26Z

1

Regexp for the rescue:

    String pattern = "mgth".chars()
            .mapToObj(ch -> "(?=.*" + (char) ch + ")")
            .collect(Collectors.joining());

    // ".*(?=.*m)(?=.*g)(?=.*t)(?=.*h).*"
    boolean matches = Pattern.compile(".*"+pattern+".*")
            .matcher("algorithm")
            .matches();

    System.out.println(matches);

This will match only if "algorithm" contains all characters in generated pattern from target string.

EDIT

Also, you can sort both strings, and perform comparison only in interval of [min("mgth"), max("mgth")] char values.

edited Jul 14, 2019 at 19:47

answered Jul 14, 2019 at 19:20

uptoyou

1,83723 silver badges27 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

Ishaan Javali · Accepted Answer · 2019-07-14 20:16:07Z

1

There is a more efficient way by using a Set.

String x = "algorithm";
String y = "mgth";
Set<Character> set = new HashSet<>();

for(char c: y.toCharArray())
   set.add(c);
for(char c: x.toCharArray())
   set.remove(c);

if(set.size() == 0) 
    System.out.println("X contains Y");
else 
    System.out.println("X does not contain Y");

What the above code does is add the characters in the smaller String to the set. Then, it removes each of the characters in the larger String.

If there are any leftover characters in the Set, then that means that the smaller String contained a letter that was not in the larger String.

edited Jul 14, 2019 at 20:16

answered Jul 14, 2019 at 18:56

Ishaan Javali

1,7133 gold badges16 silver badges23 bronze badges

2 Comments

Tibrogargan Over a year ago

Be careful of using String instead of character there - you don't actually want a set of String. You could also do

Set<Character> ySet = new HashSet<>(y.toCharArray()); Set<Character> intersection = (new HashSet<>(set)).retainAll(ySet); if (intersection.size <> ySet.size())

Tibrogargan Over a year ago

Actually, the toCharArray thing won't work. It'll produce List<char[]> Probably should use something more like y.chars().mapToObj(c->(char) c).collect(Collectors.toList());

Hasasn · Accepted Answer · 2019-07-15 10:01:35Z

1

Try this one

@Test
public void similarity() {
  String x = "algorithm";
  String y = "mgth";
  final boolean ohYes =
      y.chars().filter(yc -> x.chars().anyMatch(xc -> yc == xc)).count() == y.length();
  Assert.assertTrue(ohYes);
}

answered Jul 15, 2019 at 10:01

Hasasn

9389 silver badges10 bronze badges

2 Comments

uptoyou Over a year ago

this will return true if at least one character in X is equal. The question is about all Y characters equation.

Hasasn Over a year ago

Nope, all characters, see the y.lenght() equality.

Collectives™ on Stack Overflow

Algorithm for text similarity search

3 Answers 3

Comments

2 Comments

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

Comments

2 Comments

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related