CODEWITHSUNDEEP
c++string
TNT_42
TNT_42

Reputation: 53

C++ checking two strings content efficiency

assuming I have the following two strings:

string s1 = //some string

string s2 = //some string

how to efficiently check if s1 differs from s2 by just 1 letter? (if s1 length == s2 length)

how to efficiently check if s1 differs from s2 by 1 insertion of a letter?

how to efficiently check if s1 differs from s2 by 1 deletion of a letter?

how to efficiently check if s1's letters can be consecutively paired and swap to equal content of s12?

Upvotes: 0

Views: 69

Answers (1)

Paul Belanger
Paul Belanger

Reputation: 2434

For the first question, consider iterating over each letter pair, and keeping a count of letter pairs which differ. If your total count is equal to 1, then the condition is satisfied. (eg. use a for(int i = 0; i < s1.length(); ++i) )

For the second question, first check if s1.length() == s2.length() + 1. Then, iterate through letter pairs until you find the first pair that does not match. Then, advance your index for s1 by 1, so you're comparing s1[i+1] to s2[i]. If the remainder of the pairs chosen in this way match, then we know the s1 is formed from s2 by an insertion of a single letter.

For the third question, we can do the same thing, but swap s1 and s2.

For the last question, consider counting up the occurence of each character in both strings. If they have the same count of each character, then you will be able to do pairwise swaps to make one from the other (a result from group theory -- "Every permutation may be expressed as a product of transpositions").

All of these operations are O(n), which is as good as you can get for string comparison.

Upvotes: 2

Related Questions