samedi 28 mars 2015

fast way for string comparison

I have a simple question but it makes me confused.


I have two strings, and I want to count how many different characters between the two. The strings are sorted, equal length. Do not split the strings.


For example



input: abc, bcd
output: 2, because a and d are different characters

input: abce, bccd
output: 4, because a, c, d and e are different.


I know I can do it in O(N2), but how can I solve it in O(N) for these sorted strings?


Aucun commentaire:

Enregistrer un commentaire