using System;

​

public class Program

{

    /*

    This is your coding interview problem for today.

​

This problem was asked by Microsoft.

​

Given a 2D matrix of characters and a target word, write a function that returns whether the word can be found in the matrix by going left-to-right, or up-to-down.

​

For example, given the following matrix:

​

[['F', 'A', 'C', 'I'],

 ['O', 'B', 'Q', 'P'],

 ['A', 'N', 'O', 'B'],

 ['M', 'A', 'S', 'S']]

and the target word 'FOAM', you should return true, since it's the leftmost column. Similarly, given the target word 'MASS', you should return true, since it's the last row.

    */

    public static bool WordExists(char[][] matrix, string target)

    {

        if (target.Length > matrix.Length && target.Length > matrix[0].Length)

            return false;

        int tarIdx = 0;

        for (int row = 0; row < matrix.Length; row++)

        {

            for (int col = 0; col < matrix[row].Length; col++)

            {

                char letter = matrix[row][col];

                if (letter == target[tarIdx])

                {

                    tarIdx++;

                    if (tarIdx == target.Length)

                        return true;

                }

                else

                {

                    tarIdx = 0;

                }

            }

        }

​

        tarIdx = 0;

        for (int col = 0; col < matrix[0].Length; col++)

        {

            for (int row = 0; row < matrix.Length; row++)

            {

                char letter = matrix[row][col];

                if (letter == target[tarIdx])

                {

                    tarIdx++;

                    if (tarIdx == target.Length)

                        return true;

                }

                else

                {

                    tarIdx = 0;

                }

            }

        }

​

        return false;

    }

​

    public static void Main()

    {

        Console.WriteLine(WordExists(new char[][]{new char[]{'F', 'A', 'C', 'I'}, new char[]{'O', 'B', 'Q', 'P'}, new char[]{'A', 'N', 'O', 'B'}, new char[]{'M', 'A', 'S', 'S'}}, "ACI"));

    }

}