This updated information has been further expanded upon on my new website. You can find the updated details here: https://k5kc.com/cs/algorithms/rotate-string-problem/.
Problem :
Given two strings1
ands2
how will you check ifs1
is a rotated version ofs2
?
OR
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.ie: 'waterbottle' is a rotation of 'erbottlewat'
Example
s1 = "kodeknight" , then s2 can beodeknightk OR deknightko OR eknightkod and so on.
i.e. rotating the string 1,2,3 and so on charcters.
Solutions
Method 1 - Club one of the string and rely upon substring method
Here is the solution :
- First make sure
s1
ands2
are of the same length. - Check to see if
s2
is asubstring
ofs1 concatenated with s1
.
boolean checkRotation(string s1, string s2) if( len(s1) != len(s2)) return false if( substring(s2,concat(s1,s1)) return true return false endIn Java:
boolean isRotation(String s1,String s2) { return (s1!=null && s2!=null && s1.length() == s2.length()) && ((s1+s1).indexOf(s2) != -1); }
Method 2 - Use char[] array scan
However if this doesn't clicks to the person's mind, then we can use modulo operator method.
- Let s1 = char[] a, and s2 = char b[].
- Find index of b[0] in a. You may get single index called IN or no index or multiple index.
- In case of no index, you can simply return false.
- In case of single index, you can check if a[IN+1] = b[1] and so on. If at any point mismatch happens, you can simply return the value.
- In case of multiple index, same procedure is repeated as for single index, but for multiple time.
References - stackoverflow ,
0 comments:
Post a Comment