algorithm - 如何在矩阵中找到一个单词，其中每个字符都在唯一的行上

Question

例如:

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

现在单词“may”是可能的，因为“m”在第 1 行，“a”在第 2 行，“y”在第“3”行

但是，'tin' 是不可能的，因为 i 和 t 有一个共同的行。

注意:输入字符不必按行顺序排列。 tin 也可以是输入中的 int。假设字符数与矩阵中的行数相同。

简化版: 假设输入单词中没有字符重复(例如:may、tin)

复杂版本: 字符可以重复:(例如:tat)

Answer 1

    // 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.