How to write a character matching algorithm in JavaScript?

Question

Given this input s1 = "dadxx" s2 = "ddxx" I'd expect the output to contain a bunch of a,b pairs wherever each character in s1 matched a character in s2 and vice versa (duplicates allowed). Among those pairs would be 0,0 because s1[0] and s2[0] are both equal to d.

The problem is that my output doesn't contain 2,1 even though s1[2] and s2[1] are both equal to d.

Can someone fix my algorithm or make a better one?

Here's a JSFiddle if it helps.

Here's my code:

// For each char, see if other string contains it
s1 = 'dadxx'
s2 = 'ddxx'

matchChars(s1,s2)
matchChars(s2,s1)

function matchChars(a,b) {
    for (i = 0; i < a.length; i++) {
        found = b.indexOf(a[i])
        if (found >= 0) {
            if (a===s1) console.log(i,found)
            else console.log(found,i)
        }
    }
}

if you split them into an array of characters, I think maybe an [array intersection](http://stackoverflow.com/questions/1885557/simplest-code-for-array-intersection-in-javascript) is what you are going for? — CrayonViolent, May 12 '17 at 02:10
@CrayonViolent thanks but this more like an overachieving array intersection that finds all matches and returns their indices — Gabe Rogan, May 12 '17 at 02:16

fubar · Accepted Answer · 2017-05-12T02:46:35.170

2

I believe the problem you're having is that you're only checking for a single match for s1[i] in s2 by using indexOf. That will find the first index of a matched value, not every index.

If you instead iterate through both strings and compare every character, you get the result I think you're trying to achieve.

// Define strings
s1 = 'dadxx'
s2 = 'ddxx'

matchChars(s1,s2)
matchChars(s2,s1)

function matchChars(a,b) {
  // Convert strings to lower case for case insensitive matching
  // Remove if case sensitive matching required
  a = a.toLowerCase();
  b = b.toLowerCase();

  // Iterate through every letter in s1
  for (i = 0; i < a.length; i++) {
    // Iterate through every letter in s2
    for (j = 0; j < b.length; j++) {
      // Check if the letter in s1 matches letter in s2
      if (a[i] === b[j]) {
        // Changed per request of OP
        (a === s1) ? console.log(i, j) : console.log(j, i);
        // console.log([i, j]);
      }
    }
  }
}

Working JSBin example: https://jsbin.com/wecijopohi/edit?js,console

edited May 12 '17 at 02:46

answered May 12 '17 at 02:16

fubar

16,918
4
37
43

Nailed it. Thanks!! – Gabe Rogan May 12 '17 at 02:17
Only issue is that there are duplicates. – fubar May 12 '17 at 02:20
Hm why did you delete your last comment then? (about false positives `1,0` and `1,2`) – Gabe Rogan May 12 '17 at 02:21
I've just output the letters being matched with the index, and the letters were correct. I'm just looking at it again. https://jsbin.com/wecijopohi/edit?js,console – fubar May 12 '17 at 02:22
There's a mistake in it somewhere, because the index `1` in `a` should never be matched. But my code is showing that as a `d` instead of an `a`. Something peculiar is happening. – fubar May 12 '17 at 02:23
Ok feel free to make a new answer or revise. I'll wait. – Gabe Rogan May 12 '17 at 02:24
1

I don't see any errors or duplicates in your code. You're just calling `matchChars` twice with swapped parameters. – 4castle May 12 '17 at 02:26
D'oh. Everything is fine. I've just noticed the function is called twice with the string order switched!!! Ignore all previous comments. – fubar May 12 '17 at 02:26
It has been a long week. That's my excuse and I'm sticking to it. – fubar May 12 '17 at 02:26
Please revise your `console.log` line to this and I'll mark it correct: `if (a === s1) console.log(i, j);` `else console.log(j, i)` – Gabe Rogan May 12 '17 at 02:40

score 1 · Answer 2 · answered May 12 '17 at 03:09

You say duplicates are allowed but not required. I'm submitting this as a more modern approach, not as a correction to the accepted solution, which looks good to me. https://jsfiddle.net/avc705zr/3/

match = (a, b) => {
  let re, match, matches = []
  a.split('').forEach((l, i) => {
    re = new RegExp(l, 'g')
    while ((match = re.exec(b)) != null) {
      matches.push([i, match.index])
    }
  })
  return matches
}

However, in my experience when you actually need functionality like this, you only need one of the strings to exhausted. In other words, you are looking for matches in string 2 of all instances in string 1 -- which is to say, unique characters in string 1. So a modification which might come up in the real world might instead be like:

Array.prototype.unique = function() {
  return this.filter(function (value, index, self) { 
    return self.indexOf(value) === index;
  });
}

match = (a, b) => {
  let re, match, matches = []
  a.split('').unique().forEach(l => {
    re = new RegExp(l, 'g')
    while ((match = re.exec(b)) != null) {
      matches.push([l, match.index])
    }
  })
  return matches
}

Thanks! Another optimization (for your first answer) might be to only perform the comparison on [unique pairs](http://stackoverflow.com/questions/10505286/how-can-i-iterate-over-all-unique-pairs-of-entries-in-an-object). — Gabe Rogan, May 12 '17 at 03:36

How to write a character matching algorithm in JavaScript?

2 Answers2