Home » Technical Interview Questions » String Interview Questions » Check if all rows of a matrix are circular rotations of each other

Check if all rows of a matrix are circular rotations of each other


Given a matrix, write a function to find whether all rows are circular rotations of each other or not

Example

INPUT
s[3][3] =  a b c
c b a
a c b

OUTPUT
FALSE

As we can see in second row(ie, c b a) is not a rotated or circular permutation of  a b c

Algorithm

1. Create a string with first row elements and concatenate the string with itself.

2. Now, traverse through all the remaining rows, check if the current row string is a substring of concatenated string or not.

3. If yes, return TRUE

C++ Program

#include <bits/stdc++.h>
#include <string>
#include <sstream>
using namespace std;
#define n 3
 
//checks whether all row are rotations of each other or not
bool arePermutations(int s[n][n])
{

    ostringstream os ;
    //To concatenate strings
    string c = "";
    for (int i = 0 ; i < n ; i++)
    {
        os<<s[0][i];
        c = c + "-" + os.str();
        os.str("");
        os.clear();

    }
 
    //concatenate strings
    c = c + c;

    // Start traversing remaining rows
    for (int i=1; i<n; i++)
    {
        // Store the matrix into vector in the form
        // of strings
        string temp = "";
        for (int j = 0 ; j < n ; j++)
        {
            os<<s[i][j];
            temp = temp + "-" + os.str();
            //clearing data in osstream
            os.str("");
            os.clear();
        }
 
        // Check if the current string is present in
        // the concatenated string or not
        if (c.find(temp) == string::npos)
            return false;
    }
 
    return true;
}
 

int main()
{
    int s[n][n] = {{1, 2, 3},
        {3, 1, 2},
        {2, 3, 1}
    };
    if(arePermutations(s))
    { 
        cout << "Yes";
    }
    else
    {
        cout << "No";
    }
    return 0;
}

Try It

 

READ  Edit Distance
Array Interview Questions
Graph Interview Questions
LinkedList Interview Questions
String Interview Questions
Tree Interview Questions
Core Java Interview Questions

AD Blocker Detected !

Advertisements help running this website for free.

To view the content please disable AdBlocker and refresh the page.

Wait !!!

You can Crack Technical Interviews of Companies like Amazon, Google, LinkedIn, Facebook, PayPal, Flipkart, etc

Anisha was able to crack Amazon after practicing questions from TutorialCup