0

我为所有方向创建了一个单词求解器。它可以水平、垂直和反向查找单词。但是，我在让它向各个方向发展时遇到了问题。所以用“你好”表示：

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;
}
}
4

4 回答 4

2

这是一种有趣的思考方式：找到单词类似于解决迷宫。'start' 和 'end' 对应于您要查找的单词的开头和结尾，'dead end' 对应于路径与您的单词之间的不匹配，而 'success' 是沿着您的路径的字符串是一场比赛。

这里的好消息是有很多关于解迷宫算法的资源。我熟悉且不难实现的一种特定算法是使用回溯进行递归。

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

于 2011-04-30T22:23:11.603 回答
0

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

于 2011-04-30T22:29:20.537 回答
0

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"}，并且您使用 调用verifyWord()，str="hel"您希望返回值 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())?

于 2011-04-30T22:51:26.723 回答
0

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

#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;
}

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

于 2015-10-01T14:05:45.283 回答