单词解算器 - 所有方向

Question

我创建了一个适用于所有方向的单词解算器。它可以水平、垂直和反向查找单词。然而，我在让它朝各个方向发展时遇到了问题。因此，将“你好”纳入：

H  E  i  l
x  L  p  q
c  L  O  m

任何人都可以指出我该怎么做吗？这是我搜索单词的算法（在 C++ 中）：

/*
 * For loops that search each row, each column in all 8 possible directions.
 */
void Scramble::solve() {

cout << "Output:" << endl;

for (int row = 0; row < getRows(); row++) {
    for (int col = 0; col < getCols(); col++)
        for (int rowDir = -1; rowDir <= 1; rowDir++)
            for (int colDir = -1; colDir <=1; colDir++)
                if (rowDir != 0 || colDir != 0)
                    findWords(row, col, rowDir, colDir);
}
}

/*
 * Finds the matches in a given direction. Also calls verifyWord() to verify that the
 * current sequence of letters could possibly form a word. If not, search stops.
 */
void Scramble::findWords(int startingRow, int startingCol, int rowDir, int colDir) {

int searchResult;
string sequence = "";
sequence = sequence + wordsArr[startingRow][startingCol];

for (int i = startingRow + rowDir, j = startingCol + colDir; i >= 0 && j >= 0
&& i < getRows() && j < getCols(); i = i + rowDir, j = j + colDir) {

    sequence = sequence + wordsArr[i][j];

    if (sequence.length() >= 3) {

        searchResult = verifyWord(words, sequence);

        if ((unsigned int)searchResult == words.size())
            break;

        if (words[searchResult].rfind(sequence) > words[searchResult].length())
            break;

        if (words[searchResult] == (sequence))
            cout << sequence << endl;
    }
}
}

/*
 * Performs the verifyWord search method.
 * Searches the word to make sure that so far, there is possibly that the current sequence
 * of letter could form a word. That is to avoid continuing to search for a word
 * when the first sequence of characters do not construct a valid word in the dictionary.
 *
 * For example, if we have 'xzt', when this search is done it prevents the search
 * to continue since no word in the dictionary starts with 'xzt'
 */
int Scramble::verifyWord(vector<string> words, string str) {

int low = 0;
int mid = 0;
int high = words.size();

while (low < high) {

    mid = (low + high) / 2;

    if (str > words[mid]) {
        low = mid + 1;
    }

    else if (str < words[mid]) {
        high = mid - 1;
    }

    else
        return mid;
}
}

Answer 1

这是一个有趣的思考方式：找到这个词就像解决迷宫一样。 “开始”和“结束”对应于您要查找的单词的开头和结尾，“死胡同”对应于路径和您的单词之间的不匹配，“成功”是当字符串沿着您的路径时是一场比赛。

好消息是有很多关于迷宫求解算法的资源。我熟悉的一种特殊算法，并且实现起来并不太困难，它是 带回溯的递归。

显然，必须进行一些更改才能解决您的问题。例如，您不知道从哪里开始，但幸运的是这并不重要。您可以检查每个可能的起始位置，其中许多位置无论如何都会由于不匹配而在第一步中被丢弃。

Answer 2

1) 目前，您的 solve() 函数从每个点开始在一条直线中查找单词：这是您想要的吗？我只是问，因为“你好”在你的样本矩阵中没有显示为直线：

H  E  i  l
x  L  p  q
c  L  O  m

如果你确实想要直线单词，那么很好（这就是我一直理解这些谜题无论如何都可以工作），但如果实际上你想在蛇中找到单词-明智的时尚，然后像 Zilchonum 和 BlueRaja 这样的递归搜索建议将是一个不错的选择。只是要小心，不要最终循环回到已经使用过的字母。

2) 无论哪种情况，您的 verifyWord() 函数也存在一些问题：至少在退出 while (low < high) 的情况下它需要返回一些值循环。

即便如此，它仍然无法完全按照您想要的方式执行：例如，说您的字典
包含 {"ant", "bat" "hello", "yak", "zoo"}，并且您使用 str="hel 调用 verifyWord() "，您希望返回值 2，但目前它是这样做的：

step  low   mid  high
 0     0     0     5   // initialise
 1     0     2     5   // set mid = (0+5)/2 = 2... words[2] == "hello" 
 2     0     2     1   // "hel" < "hello" so set high = mid - 1
 3     0     0     1   // set mid = (0+1)/2 = 0... words[0] == "ant"
 4     1     0     1   // "hel" > "ant" so set low = mid + 1     
 5  // now (low<high) is false, so we exit the loop with mid==0

与其将“hel”与“hello”进行比较，也许您最好将字典中的单词截断为与 str 长度相同：即比较str 到 word[mid].substr(0,str.length())？

Answer 3

只需将其视为一个图表，其中每个字母都连接到所有相邻字母，并从每个字母开始进行深度/广度优先搜索，仅接受那些字母等于您要查找的下一个字母的节点。

Answer 4

这是我写的一个简单的单词侦探程序 --->

#include<iostream>

using namespace std;

int main()
{
    int a, b, i, j, l, t, n, f, g, k;
    cout<<"Enter the number of rows and columns: "<<endl;               
    cin>>a>>b;                                                              //Inputs the number of rows and columns
    char mat[100][100], s[100];
    cout<<"Enter the matrix: "<<endl;
    for (i = 0; i < a; i++) for (j = 0; j < b; j++) cin>>mat[i][j];         //Inputs the matrix
    cout<<"Enter the number of words: "<<endl;
    cin>>t;                                                                 //Inputs the number of words to be found
    while (t--)
    {
        cout<<"Enter the length of the word: "<<endl;
        cin>>n;                                                             //Inputs the length of the word
        cout<<"Enter the word: "<<endl;
        for (i = 0; i < n; i++) cin>>s[i];                                  //Inputs the word to be found
        for (i = 0; i < a; i++)                                         //Loop to transverse along i'th row
        {
            for (j = 0; j < b; j++)                                     //Loop to transverse along j'th column
            {
                f = i;
                g = j;
                for (k = 0; s[k] == mat[f][g] && k < n; k++, g++);          //Loop to find the word if it is horizontally right
                if (k == n)
                {
                    cout<<"The coordinates and direction are ---> "<<j+1<<","<<i+1<<" right"<<endl;
                    goto A;
                }
                f = i;
                g = j;
                for (k = 0; s[k] == mat[f][g] && k < n; k++, g--);      //Loop to find the word if it is horizontally left
                if (k == n)
                {
                    cout<<"The coordinates and direction are ---> "<<j+1<<","<<i+1<<" left"<<endl;
                    goto A;
                }
                f = i;
                g = j;
                for (k = 0; s[k] == mat[f][g] && k < n; k++, f++);      //Loop to find the word if it is vertically down
                if (k == n)
                {
                    cout<<"The coordinates and direction are ---> "<<j+1<<","<<i+1<<" down"<<endl;
                    goto A;
                }
                f = i;
                g = j;
                for (k = 0; s[k] == mat[f][g] && k < n; k++, f--);      //Loop to find the word if it is vertically up
                if (k == n)
                {
                    cout<<"The coordinates and direction are ---> "<<j+1<<","<<i+1<<" up"<<endl;
                    goto A;
                }
                f = i;
                g = j;
                for (k = 0; s[k] == mat[f][g] && k < n; k++, f++, g++); //Loop to find the word if it is down right
                if (k == n)
                {
                    cout<<"The coordinates and direction are ---> "<<j+1<<","<<i+1<<" down right"<<endl;
                    goto A;
                }
                f = i;
                g = j;
                for (k = 0; s[k] == mat[f][g] && k < n; k++, f--, g--); //Loop to find the word if it is up left
                if (k == n)
                {
                    cout<<"The coordinates and direction are ---> "<<j+1<<","<<i+1<<" up left"<<endl;
                    goto A;
                }
                f = i;
                g = j;
                for (k = 0; s[k] == mat[f][g] && k < n; k++, f++, g--); //Loop to find the word if it is down left
                if (k == n)
                {
                    cout<<"The coordinates and direction are ---> "<<j+1<<","<<i+1<<" down left"<<endl;
                    goto A;
                }
                f = i;
                g = j;
                for (k = 0; s[k] == mat[f][g] && k < n; k++, f--, g++); //Loop to find the word if it is up right
                if (k == n)
                {
                    cout<<"The coordinates and direction are ---> "<<j+1<<","<<i+1<<" up right"<<endl;
                    goto A;
                }
            }
        }
        A:;                                                             //If the word has been found the program should reach this point to start the search for the next word
    }
    return 0;
}

在我的程序中，它首先检查单词的第一个字母，然后检查后续字母。如果找到该单词，则打印该单词的起始坐标以及找到该单词的方向。