Determine if one string is a rotation of another string — A conversation

Algorithm is one the fundamental components that a programmer should master. But every time I read a book about it, I see intrusive instructions about how to solve a problem using several algorithms. Well they just tell you that you should use this and that. Sure, they are brilliant ideas, but how do those ideas come up? If we do not know this process, it is hard to say we have really learned.

I’ve been reading the book “How to solve it” by George Pólya. It is a great book that shows you how to approach a problem using various steps. You can ask about certain questions and answer them to get a better chance to obtain the final solution. Although this book is about mathematics, I think it also applies for algorithms or even just problems in general. So I’d like to write the conversation I made myself to show the process of how we get an algorithm without giving intrusive instructions. These are just my humble ideas and suggestions are always welcome.

====================================================================

Assume you have a method isSubstring which checks if one word is a substring of another Given two strings, s1 and s2, write code to check if s2 is a rotation of s1 using only one call to isSubstring (i e , “waterbottle” is a rotation of “erbottlewat”).

Q: What is the unknown? What is the goal?

A: To determine if one string is a rotation of another string.

Q: What are the data? Or can you imagine any examples for this problem?

A: Eh sure. We have an example already right? waterbottle and erbottlewat.

Q: What are the conditions or restrictions?

A: We have a method isSubstring which checks if one is a substring of another. But we can only use it once…

Q: Good. Have you seen it before? Or a similar problem in a different form?

A: Eh not really…Although I did solve a problem about if a string is a substring of another. But we’ve already have the solution for it here.

Q: That’s right. Is it possible to use it?

A: Eh OK, one string is a substring of another… how can I use it on this problem…

Q: Can you use it on our data? On the strings we have here?

A: Well, waterbottle is certainly not the substring of erbottlewat…

Q: That’s true. But waterbottle can be a substring of something, right?

A: Eh sure…

Q: What could that string be like?

A: Eh something string with “waterbottle” as a part, for example XXXwaterbottleXXX.

Q: Correct. So can we create such a string?

A: Sure…waterbottlewaterbottle.

Q: OK that’s one way. Any other way?

A: ….

Q: Have you used all the data?

A: Eh no, I still have erbottlewat… Ah you mean use it twice too? OK erbottlewaterbottlewat.

Q: Look at them carefully. What do you see?

A: ….

Q: When you concatenate waterbottle twice, does the new string contain something special? Same question for concatenate erbottlewat twice…

A: Something special…Ah I see erbottlewat in waterbottlewaterbottle and waterbottle in erbottlewaterbottlewat!

Q: Correct! Now do you see a connection between this and the rotation?

A: Hmm probably, if A is a rotation of B, then B will be a substring of AA. Otherwise this is not true.

Q: This is an assumption, we have an example which satisfies the first part. Think of an example of the latter situation.

A: OK, water and erwta. Is water a substring of erwtaerwta? I guess not. Man this is a bit tricky…If you don’t start on this direction, you probably will never land on this solution.

Q: Yeah it is possible. The question gives you something to use. So just try to apply it without any complicated thought. You may find it useful. One more thing here: What if the strings have different length?

A: Well certainly they do not satisfy the conditions. But we didn’t check it yet. Ah so we should check the length first, or even check the null first! Good catch.

link to the Java code on github (I have to say the code is really simple but the concept here is a really good one):

https://github.com/jingz8804/Algorithms-and-Problems/blob/master/src/careerCup/IsRotation.java

Enhanced by Zemanta
Advertisements

2 thoughts on “Determine if one string is a rotation of another string — A conversation

    1. Thanks Kinshuk. I actually spotted a bug in my code by looking at yours. I have to check if the strings have the same length first. We should probably also check if s1 and/or s2 is null before getting their length. 🙂

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s