check whether one string is a rotation of another

medium

Last Updated - 31/08/2024

Problem Statement

Given two strings s1 and s2, write a function to determine if s2 is a rotation of s1. A string s2 is considered a rotation of s1 if it can be obtained by shifting s1 some number of characters to the left or right.

Example 1

Input: s1 = "waterbottle" , s2 = "erbottlewat"

Output: true

Example 2

Input: s1 = "hello" , s2 = "lohell"

Output: false

Solution 1: Using Concatenation

function isRotationConcat(s1, s2) {
    if (s1.length !== s2.length) return false;
    return (s1 + s1).includes(s2);
} 

const s11 = "waterbottle";
const s21 = "erbottlewat";
isRotationConcat(s11,s21);  //output: true 

const s12 = "hello";
const s22 = "lohell";
isRotationConcat(s12,s22);  //output: false

Solution 2: Using Two-Pointer Technique

function isRotationTwoPointer(s1, s2) {

    if (s1.length !== s2.length) return false;

    let i = 0, j = 0;

    while (i < s1.length) {

        while (j < s2.length && s2[j] !== s1[i]) j++;

        if (j === s2.length) return false;

        let k = i, l = j;

        while (k < s1.length && s2[l] === s1[k]) {

            k++;

            l = (l + 1) % s2.length;

        }

        if (k === s1.length) return true;

        i++;

    }

    return false;

} 

const s11 = "waterbottle";
const s21 = "erbottlewat";
isRotationTwoPointer(s11,s21);  //output: true 

const s12 = "hello";
const s22 = "lohell";
isRotationTwoPointer(s12,s22);  //output: false

Solution 3: Using a Set to Store Rotations

function isRotationSet(s1, s2) {
    if (s1.length !== s2.length) return false;
    
    const rotations = new Set();
    let temp = s1;

    for (let i = 0; i < s1.length; i++) {
        rotations.add(temp);
        temp = temp.slice(1) + temp[0];
    }

    return rotations.has(s2);
} 

const s11 = "waterbottle";
const s21 = "erbottlewat";
isRotationSet(s11,s21);  //output: true 

const s12 = "hello";
const s22 = "lohell";
isRotationSet(s12,s22);  //output: false

Solution 4: Using a Queue

function isRotationQueue(s1, s2) {
    if (s1.length !== s2.length) return false;

    const queue = [...s1];
    for (let i = 0; i < s1.length; i++) {
        if (queue.join('') === s2) return true;
        queue.push(queue.shift());
    }

    return false;
} 

const s11 = "waterbottle";
const s21 = "erbottlewat";
isRotationQueue(s11,s21);  //output: true 

const s12 = "hello";
const s22 = "lohell";
isRotationQueue(s12,s22);  //output: false

Solution 5: Using String Rotation Check

function isRotationStringRotationCheck(s1, s2) {
    if (s1.length !== s2.length) return false;

    for (let i = 0; i < s1.length; i++) {
        const rotated = s1.slice(i) + s1.slice(0, i);
        if (rotated === s2) return true;
    }

    return false;
} 

const s11 = "waterbottle";
const s21 = "erbottlewat";
isRotationStringRotationCheck(s11,s21);  //output: true 

const s12 = "hello";
const s22 = "lohell";
isRotationStringRotationCheck(s12,s22);  //output: false

Solution 6: Using String Substring

function isRotationSubstring(s1, s2) {
    if (s1.length !== s2.length) return false;

    const doubledS1 = s1 + s1;
    return doubledS1.includes(s2);
} 

const s11 = "waterbottle";
const s21 = "erbottlewat";
isRotationSubstring(s11,s21);  //output: true 

const s12 = "hello";
const s22 = "lohell";
isRotationSubstring(s12,s22);  //output: false