Daily LeetCode Challenges - Rotate Strings

Daily LeetCode Challenges - Rotate Strings

Rotate Strings

Hey There!

It has been a while since I've posted. I was doing Codewars challenges to keep up my daily streak of solving one problem a day. However, I joined a group of friends tackling LeetCode problems and will try to be more consistent daily. Today's LeetCode Challenge was titled Add Rotate String, you can find the problem here. It is rated as an easy challenge and is a string problem.

Rotate String

In the rotate string problem, you are asked to compare two arguments, an initial and a goal string. The problem asks you to determine if at any point rotating the first letter of the initial string and adding it to the end of the string would match the goal string. If so, return a Boolean value of true if the strings do match, and false if they never match.

The approach

As with previous problems, I start by understanding the arguments passed, determining if there are any edge cases, what is being returned, and creating test cases.

Parameter:

Two random strings are passed to us in this problem. Since this was an easy problem, I did not need to take into account any capital letters, numbers, or special characters. The arguments passed were strictly strings, so I did not need to worry about arrays being passed through. The initial string had to be rotated in its initial order. So if you had the word string "trings" is a valid rotation but "tsring" is not.

Returns:

Return a true if the two arguments match at any point, or false if they don't.

Examples:

For this LeetCode I went ahead and built examples to get in the habit.

"string" & "trings" => true "string" & "apple" => false "string" & "ingstr" => true

Solution Time complexity

Based on my limited knowledge of time complexities, I believe the solution I came up with is an O(n^2) time complexity.

In the solution, there is only 1 for loop and 1 slice, both with O(n) time complexities. Since the slice method is nested inside the for loop, we end up with an O(n^2) time complexity.

One thing to note: when slicing an array the time complexity is O(n). However, the V8 engine, the engine on which Node.js runs, has optimized the runtime when slicing strings to have a time complexity of O(1).

This means my solution to the rotate string problem may be an O(n) time complexity.

Solution

var rotateString = function(s, goal) {
  let newS = s
  for (let i = 0; i < s.length; i++) {
    if (newS === goal) {
      return true
    } else {
      newS = newS.slice(1) + newS[0]
    }
  }
  return false
};

Thank you for reading. Hope you learned something.

Did you find this article valuable?

Support Jamil Sinno by becoming a sponsor. Any amount is appreciated!