It is Saturday morning in the Twin Cities of Minneapolis and St. Paul. It looks like we will have a cloudy day about 10F colder than yesterday. Sooner or later winter will arrive.
Yesterday afternoon I took out a pork butt from the garage freezer and placed it in the kitchen for it to defrost. This morning after breakfast, my wife and I cut the pork into pieces and placed it into two tin foils. My wife added two different mixes of herbs and spices, some liquids and both tins went into the oven. I set the temperature to 325F. We expect to have lunch around 02:00 PM. We are debating if we will have the pork with some rice or potatoes. For simplicity we are leaning towards brown rice.
I decided to pick a random problem from the LeetCode site. I selected problem 796 Rotate String.
We are given two strings, A and B. A shift on A consists of taking string A and moving the leftmost character to the rightmost position. For example, if A = 'abcde', then it will be 'bcdea' after one shift on A. Return True if and only if A can become B after some number of shifts on A. Note: A and B will have length at most 100 characters.
We are given two strings. The idea is to rotate the first one and determine if we can generate the second one. Note that the strings are not too long.
public boolean rotateString(String A, String B) {
}
We need to develop the rotateString() function.
After reading the problem I put together a simple test scaffolding. I then read the requirements a couple times and looked like there had to be a simpler approach to get to the solution. It seemed that rotating characters or performing string manipulations would not produce the optimal solution.
abcde,cdeab main <<< A ==>abcde<== main <<< B ==>cdeab<== main <<< rotateString: true main <<< rotateString1: true main <<< rotateString2: true main <<< rotateString3: true abcde,abced main <<< A ==>abcde<== main <<< B ==>abced<== main <<< rotateString: false main <<< rotateString1: false main <<< rotateString2: false main <<< rotateString3: false aa,a main <<< A ==>aa<== main <<< B ==>a<== main <<< rotateString: false main <<< rotateString1: false main <<< rotateString2: false main <<< rotateString3: false
The screen capture of the test scaffolding appears to have four different implementations. They all seem to produce the same results.
/**
* Test scaffolding
*/
public static void main(String[] args) {
// **** open scanner ****
Scanner sc = new Scanner(System.in);
// **** read strings ****
String[] AB = sc.nextLine().split(",");
// **** close scanner ****
sc.close();
// ???? ????
System.out.println("main <<< A ==>" + AB[0] + "<==");
System.out.println("main <<< B ==>" + AB[1] + "<==");
// **** process strings and display result ****
System.out.println("main <<< rotateString: " + rotateString(AB[0], AB[1]));
// **** process strings and display result ****
System.out.println("main <<< rotateString1: " + rotateString1(AB[0], AB[1]));
// **** process strings and display result ****
System.out.println("main <<< rotateString2: " + rotateString2(AB[0], AB[1]));
// **** process strings and display result ****
System.out.println("main <<< rotateString3: " + rotateString3(AB[0], AB[1]));
}
Not much to say about the test scaffolding. We open the scanner, read and split the line with the two input strings, and call and display the function holding the required answer.
/**
* Return True if and only if A can become B after
* some number of shifts on A.
*
* Runtime: 1 ms, faster than 38.80% of Java online submissions.
* Memory Usage: 39 MB, less than 19.69% of Java online submissions.
*/
static boolean rotateString(String A, String B) {
// **** check if string lengths do not match ****
if (A.length() != B.length())
return false;
// **** check if the strings are equal ****
if (A.equals(B))
return true;
// **** ****
StringBuilder sba = new StringBuilder(A);
// **** ****
for (int i = 0; i < sba.length(); i++) {
// **** first character ****
char ch = sba.charAt(0);
// **** append character ****
sba.append(ch);
// **** remove first character ****
sba.deleteCharAt(0);
// **** comapre strings ****
if (B.equals(sba.toString()))
return true;
}
// **** strings do not match ****
return false;
}
This is my first implementation. As I mentioned, I hesitated because it felt like the brute force approach. After a couple tests I created a string builder with the value of the first string. We could have use string manipulations, but there seems to be a lot of overhead with such approach.
We now enter a loop. Take the first character and append it to the string. We then remove the first character. This completes a shift. We then check if the current version of string A matches string B. If they do, we are done and return true. Otherwise we repeat the process with the next character.
If we do process the entire string without a match, then string B could not be reproduced with shifts so we return false. This approach was accepted by LeetCode. Take a look at the statistics in the comments of the function.
/**
* Return True if and only if A can become B after
* some number of shifts on A.
*
* Runtime: 0 ms, faster than 100.00% of Java online submissions.
* Memory Usage: 36.5 MB, less than 100.00% of Java online submissions.
*/
static boolean rotateString1(String A, String B) {
// **** check if string lengths do not match ****
if (A.length() != B.length())
return false;
// **** check if the strings are equal ****
if (A.equals(B))
return true;
// **** ****
for (int i = 0; i < A.length(); i++) {
// **** starting character ****
if (A.charAt(i) != B.charAt(0))
continue;
// **** right substring of A ****
String right = A.substring(i, A.length());
// **** left substring of A ****
String left = A.substring(0, i);
// **** concatenate right to left ****
String C = right + left;
// **** compare to B and C ****
if (B.equals(C))
return true;
}
// **** strings do not match ****
return false;
}
This implementation represents my second approach. The idea is to first perform the same checks we did in the previous attempt. In the loop we traverse the first string one character at a time looking it it matches the first character in the second string. If it does not, we move on to the next character.
If the characters match, we generate a right and a left substrings. We concatenate them and check if they match the string B. The solution was accepted and the statistics are on the comments section of the function.
I did not come with a much better approach so decided to do some searching on-line.
/**
* Return True if and only if A can become B after
* some number of shifts on A.
*
* Runtime: 0 ms, faster than 100.00% of Java online submissions.
* Memory Usage: 38.7 MB, less than 26.02% of Java online submissions.
*/
static boolean rotateString2(String A, String B) {
// **** check if string lengths do not match ****
if (A.length() != B.length())
return false;
// **** check if the strings are equal ****
if (A.equals(B))
return true;
// **** concatenate A to A ****
String C = A + A;
// **** ****
return C.contains(B);
}
This approach represents a good trick for this or similar problems that you may encounter. I believe it is something to keep in your toolbox. The idea is to append string A to itself. By doing so, we have all possible character rotations. The final step is to check if string B is contained in string C. This approach was also accepted by LeetCode. Check the resulting statistics.
/**
* Return True if and only if A can become B after
* some number of shifts on A.
*
* Runtime: 0 ms, faster than 100.00% of Java online submissions.
* Memory Usage: 38.1 MB, less than 30.93% of Java online submissions.
*/
static boolean rotateString3(String A, String B) {
return A.length() == B.length() ? (A + A).contains(B) : false;
}
After additional manipulations, it is possible to get a one liner. I like clean code that is easy to understand when you or a team member is debugging or enhancing. In this case this and the previous function are the same. Please note that in general code is optimized by the compiler. Chances are that the compiler, depending on the programming language, would produce the same code. Please check the comment section associated with this final approach.
The entire code for this project can be found in my GitHub repository.
If you have comments or questions regarding this, or any other post in this blog, or if you would like for me to serve of assistance with any phase in the SDLC (Software Development Life Cycle) of a project associated with a product or service, please do not hesitate and leave me a note below. If you prefer, send me a private message using the following address: john.canessa@gmail.com. I will reply as soon as possible.
Keep on reading and experimenting. It is the best way to learn, become proficient, refresh your knowledge and enhance your developer toolset!
One last thing, many thanks to all 2724 subscribers to this blog!!!
Keep safe during the COVID-19 pandemic and help restart the world economy.
John
Twitter: @john_canessa