STRGGEN1 - EDITORIAL

editorial
, ,
1

PROBLEM LINK:

Practice
Contest

Setter: Kapil Bansal
Tester: Sankalp

DIFFICULTY:

EASY-MEDIUM

PROBLEM:

You are given a matrix of characters. The matrix has N rows and M columns. Given a string s, you have to tell if it is possible to generate that string from given matrix.
Rules for generating string from matrix are:

  1. You have to pick first character of string from row 1, second character from row 2 and so on. The (N+1)th character of string is to be picked from row 1, that is, you can traverse the rows in a cyclic manner (row 1 comes after row N).
  2. If an occurrence of a character is picked from a row, you cannot pick the same occurrence again from that row.

QUICK EXPLANATION:

The main idea of this question is to traverse cyclic the matrix and do some string manipulation to know whether the string can be generated or not.

DETAILED STEPS:

  1. Read the input as mentioned in input format.
  2. Now, traverse the string to be generated.
  3. For first char of string check whether it is present in the first row of matrix.
  4. If present then remove that char from the first row of matrix and move row to the next row (Note: if row > n then use row % n ).
  5. If not present break the traversing of the string and print No.
  6. Repeat steps 4 and 5 till the end of string is list

SOLUTIONS:

Setter's Solution 
import java.util.Scanner;
import java.util.Arrays;

class TestClass {
    public static void main(String args[] ) throws Exception {
        Scanner sc = new Scanner(System.in);
        int t = sc.nextInt();
        while(t-- >0){
            int m = sc.nextInt();
            int n = sc.nextInt();
            char[][] arr = new char[m][n];
            for(int i=0;i<m;i++){
                String s = sc.next();
                for(int j=0;j<n;j++){
                    arr[i][j] = s.charAt(j);
                }
            }
            String s = sc.next();
            char[] str = s.toCharArray();
            int[][] isVisited = new int [m][n];
            int f=0;
            for(int i=0;i<m;i++){
                for(int l=i;l<str.length;l+=m){
                    f=0;
                    for(int j=0;j<n;j++){
                        if(str[l]==arr[i][j] && isVisited[i][j]!=1){
                            isVisited[i][j]=1;
                            f=1;
                            break;
                        }
                    }
                    if(f==0)
                    break;
                }
                if(f==0)
                break;
            }
            if(f==1)
            System.out.println("Yes");
            else
            System.out.println("No");
        }
    }
}
Tester's Solution 
for _ in range(int(input())):
    n, m = list(map(int, input().split()))
    ls = []
    for i in range(n):
        ls.append(input())
    s = input()
    i = 0
    ans = True
    while len(s)!=i:
        if s[i] in ls[i%n]:
            ans = True
            ls[i%n] = ls[i%n].replace(s[i], '', 1)
        else:
            ans = False
            break
        i+=1
    if ans == True:
        print("Yes")
    else:
        print("No")

Feel free to share your approach. Suggestions are always welcomed