CODEWITHSUNDEEP
java
Shailesh200
Shailesh200

Reputation: 49

Number of rotations required to make string

This is my code to count the number of rotations. But IDK, What is the problem with it. Can anyone explain and help me out.

Test Case: Input: david vidda

Output: 2

I tried to have brute force approach but, that wasn't working even. Can anyone point out my mistake??

import java.util.*;

class solution{
    public static int arrayLeftRotation(StringBuilder str1, StringBuilder str2) 
    {
     int i;
     int count =0;
     for (i = 0; i < str1.length(); i++){
        if(str1.equals(str2))
        { 
            count++; 
            str1 = leftRotatebyOne(str1); 
            System.out.println(str1);
        }
        else return count;
     }

        return count;
    }

    static StringBuilder leftRotatebyOne(StringBuilder str) 
    {
        int i;
        char temp = str.charAt(0);
        for (i = 0; i < str.length()-1; i++)
            str.setCharAt(str.indexOf(str.charAt(i)+""),str.charAt(i+1));
        str.setCharAt(i,temp);
        return str;
    }

    public static void main(String[] args)
    {
        Scanner in = new Scanner(System.in);
        String strr1= in.nextLine();
        StringBuilder str1  = new StringBuilder(strr1);
        String strr2 = in.nextLine();
        StringBuilder str2  = new StringBuilder(strr2);
        System.out.print(arrayLeftRotation(str1, str2));
    }
}

Upvotes: 1

Views: 499

Answers (4)

Alex M
Alex M

Reputation: 915

The trick is to append the input string to itself, then call String#indexOf. It will give you the index at which the doubled string contains the expected string, which is what you're looking for.

Example:

public static int numberOfRotations(String input, String expected) {
    final String doubledInput = input + input;
    return doubledInput.indexOf(expected);
}

If you really want to implement it yourself, you need to simplify your code to minimize the possibility of making mistakes.

public static String rotate(String input) {
    return input.substring(1) + input.charAt(0);
}

public static int numberOfRotations(String input, String expected) {
    // handle edge cases (null, empty, etc.) here
    String rotatedInput = input;
    int count = 0;
    while (!rotatedInput.equals(expected) && count < input.length()) {
        rotatedInput = rotate(rotatedInput);
        count++;
    }
    return count == input.length() ? -1 : count;
}

Upvotes: 2

Hearen
Hearen

Reputation: 7838

I am just trying to point out where your error lies and fix it.

Your error lies here in your leftRotatebyOne:

for (i = 0; i < str.length()-1; i++) 
   str.setCharAt(str.indexOf(str.charAt(i)+""),str.charAt(i+1)); // your error while shifting to the left;

What you are trying to do is shifting one position to the left, and you should just do it as:

for (i = 0; i < str.length()-1; i++) 
   str.setCharAt(i,str.charAt(i+1));

And then your method will work.

But I have to say Alex M has provided a cleaner solution to your problem. Perhaps you should have a try.

Your solution then can be (after the fix):

public class RotationCount {
    public static int arrayLeftRotation(StringBuilder str1, StringBuilder str2) {
        int i;
        int count = 0;
        for (i = 0; i < str1.length(); i++) {
            if (!str1.toString().equals(str2.toString())) {
                count++;
                str1 = leftRotatebyOne(str1);
            } else return count;
        }
        return count;
    }

    static StringBuilder leftRotatebyOne(StringBuilder str) {
        int i;
        char temp = str.charAt(0);
        for (i = 0; i < str.length() - 1; i++) {
            str.setCharAt(i, str.charAt(i + 1));
        }
        str.setCharAt(i, temp);
        return str;
    }

    public static void main(String[] args) {
        StringBuilder str1 = new StringBuilder("david");
        StringBuilder str2 = new StringBuilder("vidda");
        System.out.print(arrayLeftRotation(str1, str2));
    }
}

Upvotes: 1

benjamin c
benjamin c

Reputation: 2338

Another possible solution for arrayLeftRotation,

public static int arrayLeftRotation(String str1, String str2) {
    StringBuilder builder = new StringBuilder(str1);
    for (int i = 0; i < str1.length(); i++) {
        builder.append(str1.charAt(i)).delete(0, 1);
        if (str2.equals(builder.toString())) {
            return i + 1;
        }
    }
    return -1;
}

Note: this will return -1 if no matches found.

Upvotes: 2

Robert Kock
Robert Kock

Reputation: 6028

Your method leftRotateByOne appears more complicated than necessary. Try this:

public class Solution
{
  public static int arrayLeftRotation(String str1,
                                      String str2)
  {
    int nr_rotate;
    int counter;
    nr_rotate = 0;
    for (counter = 0; counter < str1.length(); counter++)
    {
      if (str1.equals(str2))
        return (nr_rotate);
      else
      {
        str1 = leftRotateByOne(str1);
        nr_rotate++;
        System.out.println(str1);
      }
    }

    // No possible solution
    return (-1);

  } // arrayLeftRotation

  public static String leftRotateByOne(String str)
  {
    return (str.substring(1) + str.charAt(0));
  }

  public static void main(String[] args)
  {
    String str1 = "david";
    String str2 = "vidda";
    System.out.print(arrayLeftRotation(str1, str2));
  }

} // class Solution

Upvotes: 3

Related Questions