Given a matrix of n*n size, the task is to find whether all rows are circular rotations of each other or not.
Examples:
Input: mat[][] = 1, 2, 3
3, 1, 2
2, 3, 1
Output: Yes, All rows are rotated permutation of each other.
Input: mat[3][3] = 1, 2, 33, 2, 1
1, 3, 2
Output: No, Explanation : As 3, 2, 1 is not a rotated or circular permutation of 1, 2, 3
The idea is based on the below article.
A Program to check if strings are rotations of each other or not
Steps :
- Create a string of first row elements and concatenate the string with itself so that string search operations can be efficiently performed. Let this string be str_cat.
- Traverse all remaining rows. For every row being traversed, create a string str_curr of current row elements. If str_curr is not a substring of str_cat, return false.
- Return true.
Below is the implementation of the above steps.
Java
// Java program to check if all rows of a matrix// are rotations of each otherclass GFG{ static int MAX = 1000; // Returns true if all rows of mat[0..n-1][0..n-1] // are rotations of each other. static boolean isPermutedMatrix(int mat[][], int n) { // Creating a string that contains // elements of first row. String str_cat = ""; for (int i = 0; i < n; i++) { str_cat = str_cat + "-" + String.valueOf(mat[0][i]); } // Concatenating the string with itself // so that substring search operations // can be performed on this str_cat = str_cat + str_cat; // Start traversing remaining rows for (int i = 1; i < n; i++) { // Store the matrix into vector in the form // of strings String curr_str = ""; for (int j = 0; j < n; j++) { curr_str = curr_str + "-" + String.valueOf(mat[i][j]); } // Check if the current string is present in // the concatenated string or not if (str_cat.contentEquals(curr_str)) { return false; } } return true; } // Drivers code public static void main(String[] args) { int n = 4; int mat[][] = {{1, 2, 3, 4}, {4, 1, 2, 3}, {3, 4, 1, 2}, {2, 3, 4, 1} }; if (isPermutedMatrix(mat, n)) { System.out.println("Yes"); } else { System.out.println("No"); } }}/* This code contributed by PrinciRaj1992 */ |
Output
Yes
Time complexity: O(n3)
Auxiliary Space: O(n)
Please refer complete article on Check if all rows of a matrix are circular rotations of each other for more details!
