Rotate String


  • 0

    Click here to see the full article post


  • 3
    S

    I think there is much easier solution:
    public boolean rotateString(String A, String B) {
    return (A+A).contains(B)&&(A.length==B.length);
    }


  • 0
    K

    Sway26, by simple you meant the Time Complexity is O(1) ?
    If so @Awice does this sound good to you ?
    I am just a beginner here, and would love to know what you think about Sway26's post.


  • 0
    J

    Also did an approach similar to @sway26. If you count copying memory, it's O(N). If not, it's O(1).


  • 0
    D
    public boolean rotateString(String A, String B) {
      String C = A + A;
      return C.contains(B);
    }
    

  • 0
    R
    class Solution {
        public boolean rotateString(String a, String b) {
            for(char x : a.toCharArray()){
                String firstLetter = a.substring(0,1);
                String otherLetters = a.substring(1, a.length());
                a = otherLetters + firstLetter;
                if(a.equals(b)){
                    return true;
                }
            }
            return false;
        }
    }
    

  • 0
    9

    return (A+A).contains(B);


  • 0
    K

    We can concatenate string A to itself (A+A) and find if it contains B
    for eg, temp = A+A, then temp.contains(B)


  • 0
    H

    This is a problem mentioned in Programming Pearls by John Bentley in the "Aha" algorithms category. The simplest way in terms of code is to concatenate the rotated word to itself and check if the test word is contained in it for a solution that is O(2n) in terms of space and the time complexity of whatever your string contains function which is python is sublinear (see: https://stackoverflow.com/questions/18139660/python-string-in-operator-implementation-algorithm-and-time-complexity).


  • 0
    E

    C# Solution:
    public class Solution {
    public bool RotateString(string A, string B) {
    if (A.Length != B.Length)
    return false;

            var temp = new StringBuilder();
            temp.Append(A);
            for (int s = 0; s < A.Length; s++)
            {
                temp.Remove(0, 1);
                temp.Append(A[s]);
                if (temp.ToString() == B)
                    return true;
            }
    
            return false;
    }
    

    }


  • 0
    S

    class Solution {
    public boolean rotateString(String A, String B) {
    return (A+A).indexOf(B)!=-1;
    }
    }


  • 0

    Interested in the approach of rolling hash.

    I know lots of submission are using A+A.indexOf(B).
    Most likely it should be right. However how we can proof this?


  • 0
    L

    Solution in O(1):
    public boolean rotateString(String A, String B) {
    if (A.length() != B.length())
    return false;
    return (A+A).contains(B);
    }


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.