CODEWITHSUNDEEP
algorithmmatrix
JavaDeveloper
JavaDeveloper

Reputation: 5660

How to find a word in a matrix, where each character is on unique row

Eg:

row1 [ a y e m a ]
row2 [ l i t a p ]
row3 [ i y n a t ]

Now word 'may' is possible since 'm' is on row 1, 'a' is on row2 and 'y' is on row '3'

However, 'tin' is not possible since i and t have a common row.

Note: input chars do not have to be in sequence of rows. tin can also be int as in input. Assume number of chars are the same as number of rows in matrix.

Simplified version: Assume no character repeats in input word (eg: may, tin)

Complicated version: Characters can repeat: (eg: tat)

Upvotes: 1

Views: 155

Answers (2)

Anatoli Klamer
Anatoli Klamer

Reputation: 2648

    // row1 [ a y e m a ]
// row2 [ l i t a p ]
// row3 [ i y n a t ]
//i would try to remap your data to something like
var data  = new List<char>[255];

for(var i in in rows){
    for(for j in rows[i]){
        var ch =rows[i][j]// a,b,c,d 
        if(data[ch]==null){
            data[ch] = new List<int>()
        }

        data[ch].add(i); // fill in row numbers here for every character
    }
}
// you will have an array were you can find any character in constant time O(1)
[a] = [row1, row2,row3, row1];
[b] = null;
[m] = [row1]
[y] = [row1,row3]
[t] = row3
[i] = row2
[n] = row3

//after you can try to find all rownumbers and check for uniquiness
var hs = new HashSet<int>();
hs.addAll(data[m]);
hs.addAll(data[a]);
hs.addAll(data[y]);
//in C# hs will contain only unique values
hs = [row1, row2,row3]
return hs.length>="may".length;

//instead of hashset we can use groupby for cases like tat, taa etc.

Upvotes: 1

Agapito Gallart Bernat
Agapito Gallart Bernat

Reputation: 363

The algorithm in pseudocode is:

row1 [ a y e m a ]
row2 [ l i t a p ]
row3 [ i y n a t ]
key = 'may'
x = 1

while (x < N) do
  if (key[x] not in rowx) then
     return 'Not found'
  endif else then
     x = x + 1
  endelse
done 
return 'Found'

Upvotes: 0

Related Questions