Advertisement

number of matching chars in 2 strings

Started by November 18, 2018 11:20 AM
10 comments, last by rmsgrey 6 years ago

Nypyren's solution is a good one.

For comparison, my first thought is to sort both strings and then iterate through them (advancing whichever is behind when they aren't equal; both when they are):

 


#include <algorithm>
using namespace std;
  
int counthits(string pass, string guess)
{
  sort(pass.begin(), pass.end()); //in place sort - make a copy if you want to keep the original
  sort(guess.begin(), guess.end());
  int i=0;
  int j=0;
  int count=0;
  while (i<pass.length()&&j<guess.length())
  {
    if (pass[i]==guess[j])
    {
      i++;
      j++;
      count++;
    }
    else
    {
      if (pass[i]<guess[j])
        i++;
      else //pass[i]>guess[j]
        j++;
    }
  }
  return count;
}
        
  

You could get fancier, pad both sorted strings with an extra character to prevent overflow (adjusting the while loop's end conditions to ".length()-1"), and remove the "else"s (replacing the second with the obvious if condition) and potentially advance both i and j twice each time through the loop (for example with a guess of "cad" for pass "bad" you'd compare abd~ with acd~ so count and increment both, then abd~ with acd~ so increment i, then abd~ with acd~ so increment j. I use ~ here for padding because it's ASCII 126, so won't compare less than valid guess characters (if you allow a wider range of characters, you would want to use the last valid character (or greater) - or double-pad the pass string to prevent overflow)

This topic is closed to new replies.

Advertisement