Table of Contents
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
- Create a string with first row elements and concatenate the string with itself.
- Now, traverse through all the remaining rows, check if the current row string is a substring of concatenated string(s) or not.
- 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.