Word Solver -所有方向

Question

我创建了一个用于所有方向的单词求解器。它可以在水平方向、垂直方向和反向方向查找单词。然而，我在让它向所有方向发展时遇到了问题。所以把"hello“放在下面：

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

1)目前，您的solve()函数在直线上查找从每个点开始的单词:这是您想要的吗？我之所以问这个问题，是因为'hello‘在你的样本矩阵中不是直线：

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

如果你确实只想要直线单词，那好(这就是我一直认为these puzzles的工作方式)，但如果你实际上想以蛇形的方式查找单词，那么像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

与其将"hello“与”hello“进行比较，不如将字典中的单词截断为与str相同的长度:即将str与word[mid].substr(0,str.length())进行比较

Answer 2

这里有一个有趣的思考方式:找到这个单词类似于解决一个迷宫。“start”和“end”对应于您正在查找的单词的开头和结尾，“死胡同”对应于路径和单词之间的不匹配，而“成功”是指路径上的字符串匹配。

这里的好消息是，有很多关于迷宫求解算法的资源。我熟悉的一种特殊算法是recursion with backtracking，它实现起来并不太困难。

显然，为了解决您的问题，必须进行一些更改。例如，您不知道起点在哪里，但幸运的是，这无关紧要。你可以检查每个可能的起始位置，其中许多在第一步就会因为不匹配而被丢弃。

Answer 3

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