时间戳

首页 > 解决方案 > 如何在矩阵中找到一个单词，其中每个字符都在唯一的行上

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

问题描述

例如：

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）

标签： algorithmmatrix

解决方案

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

推荐阅读