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.
PHP
<?php // PHP program to check if all rows of a // matrix are rotations of each other$MAX = 1000;// Returns true if all rows of mat[0..n-1][0..n-1]// are rotations of each other.function isPermutedMatrix( &$mat, $n){ // Creating a string that contains // elements of first row. $str_cat = ""; for ($i = 0 ; $i < $n ; $i++) $str_cat = $str_cat . "-" . strval($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 ($i = 1; $i < $n; $i++) { // Store the matrix into vector // in the form of strings $curr_str = ""; for ($j = 0 ; $j < $n ; $j++) $curr_str = $curr_str . "-" . strval($mat[$i][$j]); // Check if the current string is present // in the concatenated string or not if (strpos($str_cat, $curr_str)) return true; } return false;}// Driver Code$n = 4;$mat = array(array(1, 2, 3, 4), array(4, 1, 2, 3), array(3, 4, 1, 2), array(2, 3, 4, 1));if (isPermutedMatrix($mat, $n)) echo "Yes";else echo "No";// This code is contributed by ita_c?> |
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!
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
