Given a grid of size n x len filled with lowercase characters. We can swap two adjacent characters in the same row and column. Now we have to check whether it is possible to arrange in such a order that every row and every column in the grid is lexicographically sorted.
Examples:
Input : abcde
fghij
olmkn
trpqs
xywuv
Output : Yes
Explanation :
The grid can be rearranged as
abcde
fghij
klmno
pqrst
uvwxy
The idea to do the above problem is really simple we can simply sort the characters in the same row and then just
check column vise if the new grid is sorted column vise or not. Please not that sorting is possible with adjacent swaps (Bubble sort for example does only adjacent swaps)
- Define a function named “check” that takes a vector of strings v and an integer len as input and returns a boolean value.
- Inside the “check” function:
- Get the size of the vector v and iterate over every string in it.
- Sort every string in v in ascending order.
- Iterate from 0 to len-2 and for every iteration
- Iterate over all the strings in v.
- If the character at position j in the i-th string is greater than the character at the same position in the i+1-th string, return false.
- Iterate over all the strings in v.
- If the iterations are completed without returning false, return true
Below is the implementation of the above approach.
C++
// C++ program to check if we can make a// grid of character sorted using adjacent// swaps.#include <bits/stdc++.h>using namespace std;// v[] is vector of strings. len is length// of strings in every row.bool check(vector<string> v, int len){ int n = v.size(); for (int i = 0; i < n; i++) sort(v[i].begin(), v[i].end()); for (int i = 0; i < len-1; i++) for (int j = 0; j < n; j++) if (v[i][j] > v[i+1][j]) return false; return true;}// Driver codeint main(){ vector<string> v = { "ebcda", "ihgfj", "klmno", "pqrst", "yvwxu" }; int len = 5; // Length of strings check(v, len)? cout << "Yes" : cout << "No"; return 0;} |
Java
// Java program to check if we can make a grid// of character sorted using adjacent swaps.import java.util.Arrays;class GfG{ // v[] is vector of strings. len is // length of strings in every row. static boolean check(String[] v, int len) { int n = v.length; char[] tempArray; for (int i = 0; i < n; i++) { tempArray = v[i].toCharArray(); Arrays.sort(tempArray); v[i] = new String(tempArray); } for (int i = 0; i < len-1; i++) for (int j = 0; j < n; j++) if (v[i].charAt(j) > v[i+1].charAt(j)) return false; return true; } // Driver code public static void main(String []args) { String[] v = { "ebcda", "ihgfj", "klmno", "pqrst", "yvwxu" }; int len = 5; // Length of strings if (check(v, len)) System.out.println("Yes"); else System.out.println("No"); }}// This code is contributed by Rituraj Jain |
Python
# Python program to check if we can make a# grid of character sorted using adjacent# swaps.# v[] is vector of strings. len is length# of strings in every row.def check(v, l): n = len(v) for i in v: i = ''.join(sorted(i)) for i in range(l - 1): for j in range(n): if (v[i][j] > v[i + 1][j]): return False return True # Driver codev = [ "ebcda", "ihgfj", "klmno", "pqrst", "yvwxu" ]l = 5 # Length of stringsif check(v, l): print "Yes"else: print "No"# This code is contributed by Sachin Bisht |
C#
// C# program to check if we can make a grid // of character sorted using adjacent swaps.using System;class GfG { // v[] is vector of strings. len is // length of strings in every row. static Boolean check(String[] v, int len) { int n = v.Length; char[] tempArray; for (int i = 0; i < n; i++) { tempArray = v[i].ToCharArray(); Array.Sort(tempArray); v[i] = new String(tempArray); } for (int i = 0; i < len-1; i++) for (int j = 0; j < n; j++) if (v[i][j] > v[i+1][j]) return false; return true; } // Driver code public static void Main(String []args) { String[] v = { "ebcda", "ihgfj", "klmno", "pqrst", "yvwxu" }; int len = 5; // Length of strings if (check(v, len)) Console.WriteLine("Yes"); else Console.WriteLine("No"); } } // This code has been contributed by 29AjayKumar |
Javascript
<script>// Javascript program to check if we can make a grid// of character sorted using adjacent swaps.// v[] is vector of strings. len is // length of strings in every row.function check(v,len){ let n = v.length; let tempArray; for (let i = 0; i < n; i++) { tempArray = v[i].split(""); (tempArray).sort(); v[i] = (tempArray).join(""); } for (let i = 0; i < len-1; i++) for (let j = 0; j < n; j++) if (v[i][j] > v[i+1][j]) return false; return true;}// Driver codelet v = ["ebcda", "ihgfj", "klmno", "pqrst", "yvwxu" ];let len = 5; // Length of stringsif (check(v, len)) document.write("Yes");else document.write("No");// This code is contributed by rag2127</script> |
Output
Yes
Time Complexity: O(n*len*log(len))
Auxiliary Space: O(1)
This article is contributed by Sarthak Kohli. If you like neveropen and would like to contribute, you can also write an article using write.geeksforgeeks.org or mail your article to review-team@geeksforgeeks.org. See your article appearing on the neveropen main page and help other Geeks.
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!
