# Check if all Rows of a Matrix are Circular Rotations of Each Other

Difficulty Level Medium
Matrix Pattern Searching Searching StringViews 2487

## Problem Statement

In the “Check if all Rows of a Matrix are Circular Rotations of Each Other” problem we have given a char matrix, write a program to find whether all rows are circular rotations of each other or not. If all rows are circular rotations of each other print “`Yes`” else print “`No`“.

## Input Format

The first line containing two integer n and m. Here n denotes the number of rows and m denotes the number of columns of the char matrix.

The next n lines containing a string of length m or in other words we can say that every line containing m char values without space-separated.

## Output Format

Print “`Yes`” if all rows are circular rotations of each other otherwise print “`No`“.

## Constraints

• 1<=n, m<=200
• m[i][j] is any lower case character.

## Example

```3 4
abcd
dabc
cdab```
`Yes`

Explanation: Here we make a string s which form by concatenation of m[0] string with itself. So, our string s is “abcdabcd”. Now from second row to till the end row we simply check whether they are substring of string s or not. If all other rows are substring of the string s then print “`Yes`” else print “`No`“. So, here “dabc” and “cdab” are the substring of s. So, the answer is “`Yes`“.

## Algorithm to Check if all Rows of a Matrix are Circular Rotations of Each Other

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(s) or not.
3. If all the rows are substring of s then print Yes else print No.

## Implementation

### C++ program to Check if all Rows of a Matrix are Circular Rotations of Each Other

```#include <bits/stdc++.h>
using namespace std;

int check_substring(string str, string target)
{
int t = 0;
int len = str.length();
for(int i = 0; i < len; i++)
{
if(t==target.length())
break;

if(str[i]==target[t])
t++;
else
t=0;
}
int m=target.length();
if(t<m)
{
return 0;
}
else
{
return 1;
}
}

int main()
{
int n,m;
cin>>n>>m;
string a[n];
for(int i=0;i<n;i++)
{
cin>>a[i];
}
string s="";
s+=a[0];
s+=a[0];
int flag=1;
for(int i=1;i<n;i++)
{
flag = check_substring(s,a[i]);
if(flag==0)
{
break;
}
}
if(flag==0)
{
cout<<"No"<<endl;
}
else
{
cout<<"Yes"<<endl;
}
return 0;
}```

### Java Program to Check if all Rows of a Matrix are Circular Rotations of Each Other

```import java.util.Scanner;

class sum {

static int check_substring(char str[], char target[], int n, int m)
{
int t = 0;
for (int i = 0; i < n; i++) {
if (t == m)
break;
if (str[i] == target[t])
t++;
else
t = 0;
}
if(t<m)
{
return 0;
}
else
{
return 1;
}
}

public static void main(String[] args)
{
Scanner sr= new Scanner(System.in);
int n = sr.nextInt();
int m = sr.nextInt();
char [][] a= new char[n+1][m+1];
for(int i=0;i<n;i++)
{
String s = sr.next();
a[i] = s.toCharArray();
}
char [] s = new char[2*m+1];
System.arraycopy(a[0], 0, s, 0, m);
for(int i=m;i<2*m;i++)
{
s[i]=a[0][i-m];
}
int flag=0;
for(int i=1;i<n;i++)
{
flag = check_substring(s, a[i],2*m,m);
if(flag==0)
{
break;
}
}
if(flag==1)
{
System.out.println("Yes");
}
else
{
System.out.println("No");
}
}
}```
```3 4
abcd
dabc
bcda```
`Yes`

## Complexity Analysis to Check if all Rows of a Matrix are Circular Rotations of Each Other

### Time Complexity

O(n*m) where n is the number of rows in the matrix and m is the number of columns in the matrix.

### Space Complexity

O(m) where m is the number of column in the matrix. Here we define string s of size 2*m for checking the condition of substring for other row string.

Reference

Translate ยป