Programming Interview Question - String Permutation Test - C++

Programming Interview Question

Question: given two string write a method to decide if one is a permutation of the other.

This is a common question that could be easily solved if we know in advance which is the size of the alphabeth. A straightforward approach could be to sort both strings and then compare them. This approach has complexity due to sorting. We can do better and lower the complexity to  if we reason as follows: given a boolean sequence of the same size of the alphabet  initially false initialized.  Then what happen if  for each char we found in the  string we negate the value of the correnspoding bool in the sequence? We end up having the at position if the char appeared an odd number of times and otherwise. Now if the other string is a permutation of the first one, we all agree that for each char in it contains the same number of occurrences. This means that if we apply the same process as before on the boolean sequence using as input the string each bool is being negated an even number of times and this means that its value would be the same as the beginning of the process (all ). So if the sequence does not contains any true value, than it means that the strings contains the same elements i.e. they are permutation of each other.

Example:

  1. "abbccd" , "cbdabc" ,
  2. Apply negation using s
  3. Apply negation using v

 

A possible C++ implementation is shown here


template<uint SIZEALPHABETH = 256>
bool isPermutation(const std::string& v, const std::string& s){

if(v.size() != s.size())
  return false;
 bool counters[SIZEALPHABETH] = { 0 };

 for(uint j=0 ; j<s.size() ; j++){
  uint idxs= s[j]%SIZEALPHABETH;
  uint idxv= v[j]%SIZEALPHABETH;
  counters[idxs] = !counters[idxs];
  counters[idxv] = !counters[idxv];
 }
for(uint j=0 ; j<SIZEALPHABETH ; j++)
 if(counters[j])
  return false;

return true;

}

 

 

Be the first to leave a comment. Don’t be shy.

Join the Discussion

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>