面接でこの質問をされたのですが、最適な答えが気になります。質問はこのようなものです：あなたは文字で満たされたnxnボードを与えられます。ゲームアルゴリズムは、このボード上のすべての可能な単語を検索して一覧表示する必要があります。ここで、「単語」は、水平方向または垂直方向の少なくとも3文字の文字列として定義されます。これを行うための最も時間効率の良い方法は何ですか？
この質問の「単語」は、辞書からの実際の単語である必要はありません。重要なのは、許容可能な長さのすべての文字列をできるだけ速く見つけることです。ボード上のすべてのスペースを横断し、そのスペースの文字で始まるすべての文字列を見つける残忍な力のアプローチを除いて、私は他に何も考えられませんでした。これにはO（n ^ 3）時間が必要です。どうやってやるの？
PS。人々がより良い解決策があるとは思わないので、この質問は反対票を投じられたようです。ただし、これはマイクロソフトの面接の質問であり、面接官は私の答えが最適ではないと明示的に言っていました。
段階的な問題への私のアプローチは次のとおりです。
パズルで特定の単語を見つけてみてください: DFS を使用して、パズルで単語を見つけることができます。すべての行と列の文字を反復処理する必要があるため、これは O(n^2) になります。
パズルで指定されたすべての単語を見つける: x 個の単語が指定されている場合、すべての単語に対して上記のアルゴリズムを使用できます。複雑さは O(x*n^2) になります。
同じ接頭辞を持つ単語がある場合、接頭辞を検索するために行われた作業を繰り返します。これは、与えられた単語のトライ構造を構築し、トライの DFS とパズルの DFS を組み合わせることで回避できます。
以下は、C++ での最初のステップの大まかな実装です。
bool FindWordInPuzzle(int i, int j, char nextChar, int nextCharId, string word, int m, int n, bool **mark, char **maze)
{
int move[8][2] = { 0, -1, -1, -1, -1, 0, -1, 1, 0, 1, 1, 1, 1, 0, 1, -1 };
mark[i][j] = 1;
for (int r = 0; r < 8; r++) {
int g = i + move[r][0];
int h = j + move[r][1];
if (g > 0 && g < m + 2 && h > 0 && h < m + 2 && mark[g][h] == 0 && maze[g][h] == nextChar) {
nextCharId++;
if (nextCharId >= word.length()) {
return true;
}
if (FindWordInPuzzle(g, h, word[nextCharId], nextCharId, word, m, n, mark, maze)) {
return true;
}
}
}
return false;
}
bool FindWord(char **maze, bool **mark, int m, int n, string word) {
char currentChar = word[0];
int currentCharId = 0;
for (int row = 1; row < m + 2; row++) {
for (int col = 1; col < n+2; col++) {
if (maze[row][col] == currentChar && mark[row][col] == 0) {
currentCharId++;
if (currentCharId >= word.length()) {
return true;
}
if (FindWordInPuzzle(row, col, word[currentCharId], currentCharId, word, m, n, mark, maze)) {
return true;
}
}
currentCharId = 0;
currentChar = word[0];
}
}
return false;
}
int main() {
string word;
int m, n;
cin >> word;
if (word.length() <= 0) return 0;
cin >> m >> n;
char** maze;
bool **mark;
// declare arrays
maze = new char*[m + 2];
mark = new bool*[m + 2];
for (int i = 0; i < m + 2; i++) {
maze[i] = new char[n + 2];
mark[i] = new bool[n + 2];
}
// boundaries
for (int i = 0; i < m + 2; i++) {
maze[0][i] = ' ';
maze[i][0] = ' ';
maze[0][m + 1] = ' ';
maze[i][m + 1] = ' ';
mark[0][i] = 1;
mark[i][0] = 1;
mark[0][m + 1] = 1;
mark[i][m + 1] = 1;
}
// get values
for (int i = 1; i < m + 1; i++) {
for (int j = 1; j < n + 1; j++) {
cin >> maze[i][j];
mark[i][j] = 0;
}
}
bool val = FindWord(maze, mark, m, n, word);
cout << val;
cin >> word;
return 0;
}
しましょうm(x) = max {0, x}。0ベースのインデックスを使用する場合、
s(x,y) = m(x-1) + m(n-x-2) + m(y-1) + m(n-y-2)
位置から始まる単語(x,y)。水平方向に、左側に列0, 1, ..., y-2で終わるもの、右側に列で終わるものx+2, x+3, ..., n-1。縦の単語についても同様です。
2*(n-3)したがって、各位置で、と2*(n-2)単語の間から始まります（両端を含む）。
より正確には、位置で、またはの場合にのみ水平方向の単語(x,y)が始まり、それ以外の場合は単語が始まります。これにより、行ごとに水平方向の単語が作成されます。列ごとの垂直方向の単語の数は同じであるため、全体としてn-2y = 0y = n-1n-32*(n-2) + (n-2)*(n-3) = (n-1)*(n-2)
2*n*(n-1)*(n-2)
グリッド内の必ずしも明確な単語ではありません。アルファベットが小さすぎないと仮定すると、重複の割合は平均して大きくないため、以下の複雑さのアルゴリズムを持つことは不可能O(n³)です。
重複が考慮されない場合は、それだけであり、アレイをトラバースする低レベルのバリエーションのみが残ります。
重複を削除する必要があり、すべての個別の単語を可能な限り効率的にリストすることが目標である場合、問題は、どのデータ構造によって重複を可能な限り効率的に削除できるかということです。答えることはできませんが、トライはかなり効率的だと思います。
ここでの2つの問題-1つ：素朴な解決策のブルートフォースではO(n^3)なく、ですO(n^4)。
各部分文字列をリストの新しいエントリにコピーするとします。あなたにはO(n^3)言葉があります。ただし、これらはそれぞれO(n)（平均して）それ自体であるため、これらすべてのサブ文字列をリストにコピーすることは実際にはO(n^4)です。
2：
より効率的な解決策は、トライデータ構造を維持し、マトリックス内の各インデックス（右と下）からのトラバーサルのようなDFSを使用してそれを埋めることです。
これによりO(n^3)、トライをO(n^3)単語で埋める解決策が得られます。
なんで言ってるのO(n^3)？ボードは正方形で、正方形はO(n^2)です。
コードは次のとおりです。
for(int col=0; col<n-2; ++col) {
for(int row=0; row<n-2; ++row) {
// for given (row,col)
// yield word to right
// yield word down
// yield word down-right
}
}
これはO(3*n^2)です。
あなたも逆になりたいならそれはO(6*n^2)
C＃の実際のコード
class Program
{
private static Random rnd = new Random();
static void Main(string[] args)
{
string alphabet = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
char[,] letters = new char[5, 5];
int counter = 0;
// filling and printing
for (int i = 0; i < letters.GetLength(0); ++i)
{
for (int j = 0; j < letters.GetLength(1); ++j)
{
letters[i, j] = alphabet[rnd.Next(alphabet.Length)];
Console.Write(letters[i,j]);
}
Console.WriteLine("");
}
// generating "words"
for (int i = 0; i < letters.GetLength(0)-2; ++i)
{
for (int j = 0; j < letters.GetLength(1)-2; ++j)
{
// horizontally
Console.Write(counter.ToString() + ": ");
Console.Write(letters[i, j]);
Console.Write(letters[i, j+1]);
Console.Write(letters[i, j+2]);
Console.WriteLine("");
counter++;
// vertically
Console.Write(counter.ToString() + ": ");
Console.Write(letters[i, j]);
Console.Write(letters[i+1, j]);
Console.Write(letters[i+2, j]);
Console.WriteLine("");
counter++;
// diagonally
Console.Write(counter.ToString() + ": ");
Console.Write(letters[i , j]);
Console.Write(letters[i + 1, j+1]);
Console.Write(letters[i + 2, j+2]);
Console.WriteLine("");
counter++;
}
}
}
}
出力
LWIDM OWWGR APVOM GKECL TXCPD 0：LWI 1：LOA 2：LWV 3：WID 4：WWP 5：WWO 6：IDM 7：IWV 8：IGM 9：OWW 10：OAG 11：OPE 12：WWG 13：WPK 14：WVC 15：WGR 16：WVE 17：WOL 18：APV 19：AGT 20：AKC 21：PVO 22：PKX 23：PEP 24：VOM 25：VEC 26：VCD
結果の数は27=3 *（5-2）^2です