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

Difficulty Level Medium
Frequently asked in Accenture Cadence India Citadel FreeCharge Microsoft Pinterest
Matrix Pattern Searching Searching StringViews 2205

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 ยป