CODEWITHSUNDEEP
javaalgorithm
Umesh Pathak
Umesh Pathak

Reputation: 41

alternative approach to count number of rotation required to find original string from rotated string

WE got 2 strings one correct and one its rotation? we have to tell that after how many steps of rotation of 2nd string we get the original (first)string(suppose only one side rotation is allowed)

but problem here is traditional method of rotating one charater of string at a time and then comparing rotated string with original is taking more time than allowed which alternative approach can be used?

string1: david string2: vidda

(processing part-rotation first: avidd, second: david, so answer is 2) output: 2

Upvotes: 2

Views: 1309

Answers (2)

Nicola Uetz
Nicola Uetz

Reputation: 858

I don't know if my approach is fast enough... But it has a runtime of O(n) where n is the length of the strings.

This approach only works if it is given that it is solvable and if both strings have the same length:

public static void main(String[] args) {
    String string1 = "david";
    String string2 = "avidd";
    char[] a = string1.toCharArray();
    char[] b = string2.toCharArray();
    int pointer = a.length-1;
    int off = 0;
    int current = 0;
    for (int i = b.length-1; i >= 0; i--) {
        if (b[i] == a[pointer]) {   //found a match
            current++;              //our current match is one higher
            pointer--;              //pointer of string1 goes one back
        } else if (current != 0) {  //no match anymore and we have had a match
            i ++;                   //we have to recalculate the actual position in the next step of the loop
            off += current;         //we have to rotate `current` times more
            current = 0;            //reset current match
            pointer = a.length-1;   //reset pointer
        } else {                    //no match and we didn't have had a match the last time
            off ++;                 //we have to rotate one more time
        }
    }
    System.out.println("Rotate: " + off);
}

basically it starts at the end of both the strings and goes back to the beginning until it doesn't get any differences any more. If it does get a difference at any point it adds the current counter to off and recontinues at the end of string1.

My algorithm does not check if the strings are the same after having done off rotations.

Upvotes: 0

David
David

Reputation: 609

String one = "david"; 
String two = "vidda";

one.concat(one).indexOf(two)

would work wouldn't it?

Upvotes: 4

Related Questions