导入
Boggle
开发一款名为 Boggle 的游戏，从字符网格中找出字典中的单词。
题目描述
给定一个 的字符网格和一个字典，找出所有可以从网格中字符组成的、且存在于字典中的单词。
- 一个单词可以从网格中的任意字符开始和结束。
- 下一个字符必须与前一个字符在上下左右或任意对角方向相邻。
- 在构成一个单词时，网格中每个位置的字符只能使用一次。
示例
假设我们有一个 的网格和一个字典作为输入。我们可以从网格中构造出六个在字典中存在的单词。绿色高亮的字符表示它们组成了单词 "eat"，该词也存在于字典中。
在网格中，我们从字符 'E' 开始，然后向上并向左（沿对角线）移动到 'A'，再向右移动到 'T'，从而组成 "eat"。
...
示例输入
1grid = [['c', 'a', 't'], 2 ['r', 'r', 'e'], 3 ['t', 'o', 'n']] 4 5dictionary = {"cat", "cater", "cartoon", "toon", "moon", "not", "tone", "apple", "ton", "art"}
期望输出
1output = ["art", "tone", "cat", "cater", "not", "ton"]
自行尝试
C++
1#include <string> 2#include <list> 3#include <iostream> 4#include <vector> 5#include <unordered_set> 6 7using namespace std; 8 9class Boggle { 10 public: 11 // 代码假设网格的两个维度相同 12 vector<vector<char>> grid; 13 unordered_set<string> dictionary; 14 vector<vector<bool>> state; 15 16 Boggle(const vector<vector<char>>& g, const unordered_set<string>& d) 17 : grid(g), dictionary(d) { 18 // TODO: 写你的代码 19 20 } 21 22 // 挑战函数 23 unordered_set<string> FindAllWords() { 24 // TODO: 写你的代码 25 unordered_set<string> words; 26 return words; 27 } 28};
Java
1// 导入所需函数 2import java.util.*; 3 4class Pair { 5 public Integer first; 6 public Integer second; 7 8 public Pair(Integer first, Integer second) { 9 this.first = first; 10 this.second = second; 11 } 12} 13 14class Boggle { 15 // 代码假设网格的两个维度相同 16 char[][] grid; 17 Set<String> dictionary; 18 boolean[][] state; 19 20 Boggle(char[][] grid, HashSet<String> dictionary) { 21 // TODO: 写你的代码 22 } 23 24 public HashSet<String> findAllWords() { 25 // TODO: 写你的代码 26 HashSet<String> result = new HashSet<String>(); 27 return result; 28 } 29}
Python
1class Boggle: 2 # 代码假设网格的两个维度相同 3 def __init__(self, grid, dictionary): 4 self.grid = grid 5 self.dictionary = dictionary 6 self.state = [[False for x in range(len(grid))] \ 7 for y in range(len(grid))] 8 9 # TODO: 写你的代码 10 # 初始化状态 11 12 # 挑战函数 13 def find_all_words(self): 14 words = set([]) 15 # TODO: 写你的代码 16 17 return words
JS
1export class Boggle { 2 // 代码假设网格的两个维度相同 3 constructor(grid, dictionary) { 4 this.grid = grid; 5 this.dictionary = dictionary; 6 7 // TODO: 写你的代码 8 9 // 初始化状态 10 } 11 12 // 挑战函数 13 findAllWords() { 14 let words = new Set([]); 15 16 // TODO: 写你的代码 17 18 return words; 19 } 20};
Ruby
1class Boggle 2 # 代码假设网格的两个维度相同 3 attr_accessor :grid, :dictionary, :state 4 def initialize(grid, dictionary) 5 @grid = grid 6 @dictionary = dictionary 7 8 # TODO: 写你的代码 9 # 初始化状态 10 end 11 12 def find_all_words() 13 words = [] 14 # TODO: 写你的代码 15 return words 16 end 17end
Go
1package main 2 3import ( 4 "fmt" 5 "strconv" 6 "sort" 7 "math" 8 "encoding/json" 9) 10// Boggle 类型结构体 11type Boggle struct { 12 grid [][]string 13 dictionary []string 14 state [][]bool 15} 16 17// BoggleInit 初始化并返回一个 Boggle 类型对象 18// 代码假设网格的两个维度相同 19func BoggleInit(grid [][]string, dictionary []string) *Boggle { 20 21 Boggle := &Boggle{ 22 grid: grid, 23 dictionary: dictionary, 24 // TODO: 写你的代码（初始化状态） 25 } 26 27 return Boggle 28} 29 30// FindAllWords 是挑战函数 31func (b *Boggle) FindAllWords() map[string]bool { 32 words := make(map[string]bool) 33 // TODO: 写你的代码 34 return words 35}
解决方案
这是一个回溯问题。我们从网格中的一个字符开始，尝试以该字符为起点构造尽可能多的单词。然后对网格中所有字符重复此过程。
为了找到以某个字符开头的所有单词，我们使用类似于深度优先搜索的算法。由于网格中的每个字符在单词中只能使用一次，我们需要维护一个布尔矩阵来标记对应字符是否已被使用。
让我们用上述示例网格来查找字典中存在的所有单词：
优化解法
如果我们能为字典提供一个 prefix() 方法，就可以加速算法。该方法返回一个字符串是否是字典中某个单词的前缀。
考虑下面的例子：我们要找以字符 'E'（示例网格第二行第三列）开头的所有单词。
...
- 我们从 'E' 开始。根据字典，'E' 是至少一个单词的前缀，因此我们保留 'E' 并继续，同时将 'E' 标记为已使用。
- 'E' 有 5 个未使用的邻居：'A'、'T'、'R'、'O'、'N'。我们从第一个邻居 'A' 开始。'ea' 是有效前缀，因为它出现在单词 'eat' 中。
- 'A' 有 4 个未使用的邻居：'C'、'T'、'R'、'R'。
- 'E' 是 'A' 的邻居，但不考虑，因为已经使用过。
- 我们先尝试 'C'，但 'eac' 既不是有效单词，也不是字典中任何单词的有效前缀，因此我们转向下一个邻居 'T'，发现 'eat' 是一个有效单词。
- 我们将 'eat' 添加到结果列表中，然后继续探索 'T' 的邻居。此时 'T' 只有一个未使用的邻居 'R'。但 'eatr' 既不是有效单词，也不是字典中任何单词的前缀，因此我们回溯，并继续处理 'A' 的其他邻居。
- 此时剩下的是 'R' 和 'R'。我们检查 'ear'，发现它既不是有效单词，也不是有效前缀，因此我们回溯。
- 回溯时，我们始终重置已使用标志，以便当前字符可在其他路径中使用。我们再次回溯，查看 'E' 的其他邻居：'T'、'R'、'O'、'N'。我们继续直到所有从 'E' 出发的路径都被探索完毕。
通过动画可以更清楚地理解这一过程：
注意：有时面试官也可能讨论字典的实现方式。字典可以用哈希集合数据结构或 前缀树 数据结构实现。
多标签代码
C++
1#include "PrintingFunctions.h" 2 3using namespace std; 4 5class Boggle { 6 // 代码假设网格的两个维度相同 7 public: 8 vector<vector<char>> grid; 9 unordered_set<string> dictionary; 10 vector<vector<bool>> state; 11 12 Boggle(const vector<vector<char>>& g, const unordered_set<string>& d) 13 : grid(g), dictionary(d) { 14 state.resize(g.size()); 15 for (vector<bool>& v : state) { 16 v.resize(g.back().size()); 17 } 18 } 19 20 // 查找所有邻居 21 list<pair<int, int>> FindAllNeighbors(int x, int y) { 22 list<pair<int, int>> nbrs; 23 int start_x = max(0, x - 1); 24 int start_y = max(0, y - 1); 25 int end_x = min((int)(grid.size() - 1), x + 1); 26 int end_y = min((int)(grid.size() - 1), y + 1); 27 28 for (int i = start_x; i <= end_x; ++i) { 29 for (int j = start_y; j <= end_y; ++j) { 30 if (state[i][j]) { 31 continue; 32 } 33 nbrs.push_back(pair<int, int>(i, j)); 34 } 35 } 36 return nbrs; 37 } 38 39 void FindWordsRec(int i, int j, string& current, 40 unordered_set<string>& words) { 41 // 如果当前单词在字典中，则添加到结果中 42 if (!current.empty() && dictionary.find(current) != dictionary.end()) { 43 words.insert(current); 44 } 45 // 我们可以通过字典的 prefix 方法显著提升算法效率 46 /* 47 if (!dictionary.is_prefix(current)) { 48 // 如果当前单词不是字典中任何单词的前缀 49 // 我们无需继续搜索 50 return; 51 } 52 */ 53 54 // 查找所有邻居 55 list<pair<int, int>> nbrs = FindAllNeighbors(i, j); 56 57 for (auto& pr : nbrs) { 58 current += grid[pr.first][pr.second]; 59 60 // 更新状态 61 state[pr.first][pr.second] = true; 62 63 // 递归调用挑战函数处理所有邻居 64 FindWordsRec(pr.first, pr.second, current, words); 65 current.resize(current.size() - 1); 66 67 // 更新状态 68 state[pr.first][pr.second] = false; 69 } 70 } 71 72 // 挑战函数 73 unordered_set<string> FindAllWords() { 74 unordered_set<string> words; 75 string current_word; 76 for (int i = 0; i < grid.size(); ++i) { 77 for (int j = 0; j < grid.size(); ++j) { 78 // 调用递归挑战函数 79 FindWordsRec(i, j, current_word, words); 80 } 81 } 82 return words; 83 } 84}; 85 86// 打印网格的函数 87void GridPrint(vector<vector<char>> chr_lst) { 88 cout << endl; 89 for (auto chr_arr : chr_lst) { 90 cout << "["; 91 int j = 0; 92 for (char chr : chr_arr) { 93 cout << "\'" << chr << "\'"; 94 if (++j != chr_arr.size()) cout << ", "; 95 } 96 cout << "]" << endl; 97 } 98} 99 100int main() { 101 vector<vector<vector<char>>> grids = { 102 {{'c', 'a', 't'}, {'r', 'r', 'e'}, {'t', 'o', 'n'}}, 103 {{'o', 'a', 'a'}, {'e', 't', 'a'}, {'i', 'h', 'k'}}, 104 {{'a', 'b', 'i'}, {'e', 'g', 'a'}, {'r', 'r', 'o'}}, 105 {{'m', 'o', 'q'}, {'e', 'l', 'z'}, {'z', 'r', 'o'}}}; 106 107 vector<unordered_set<string>> dictionaries = { 108 {"cat", "cater", "cartoon", "toon", "moon", "not", "tone", "apple", "ton", 109 "art"}, 110 {"oath", "pea", "ate", "the", "iot"}, 111 {"ago", "ego", "bear", "gear", "rear", "big", "roar", "rig", "bar"}, 112 {"zoo", "zoom", "zoz"}}; 113 114 for (int i = 0; i < grids.size(); i++) { 115 cout << "字符网格" << endl; 116 GridPrint(grids[i]); 117 118 cout << "\n字典: "; 119 PrintList(dictionaries[i]); 120 121 Boggle b = Boggle(grids[i], dictionaries[i]); 122 unordered_set<string> words = b.FindAllWords(); 123 cout << "输出:\t"; 124 PrintList(words); 125 cout << "--------------------------------------------------------------------------------------------------\n" << endl; 126 } 127}
Java
1// 导入所需函数 2import java.util.*; 3 4class Main { 5 public static void main(String[] args) { 6 char[][][] grids = {{{'c', 'a', 't'}, {'r', 'r', 'e'}, {'t', 'o', 'n'}}, 7 {{'o', 'a', 'a'}, {'e', 't', 'a'}, {'i', 'h', 'k'}}, 8 {{'a', 'b', 'i'}, {'e', 'g', 'a'}, {'r', 'r', 'o'}}, 9 {{'m', 'o', 'q'}, {'e', 'l', 'z'}, {'z', 'r', 'o'}}}; 10 11 String[][] dictionaries = 12 {{"cat", "cater", "cartoon", "toon", "moon", "not", "tone", "apple", "ton", "art"}, 13 {"oath", "pea", "ate", "the", "iot"}, 14 {"ago", "ego", "bear", "gear", "rear", "big", "roar", "rig", "bar"}, 15 {"zoo", "zoom", "zoz"}}; 16 17 for (int i = 0; i < grids.length; i++) { 18 HashSet<String> dictionary = new HashSet<String>(Arrays.asList(dictionaries[i])); 19 System.out.print("字符网格"); 20 21 // 自定义函数打印网格 22 BogglePrint.gridPrint(grids[i]); 23 24 // 使用自定义函数打印字符串数组 25 System.out.println("\n字典: {" + BogglePrint.arrPrint(dictionary) + "}"); 26 Boggle b = new Boggle(grids[i], dictionary); 27 HashSet<String> words = b.findAllWords(); 28 29 // 使用自定义函数打印字符串数组 30 System.out.println("输出:\t[" + BogglePrint.arrPrint(words) + "]"); 31 System.out.println( 32 "--------------------------------------------------------------------------------------------------\n"); 33 } 34 } 35}
Python
1from boggle import * 2from printing_functions import * 3 4def main(): 5 grids = [[ ['c', 'a', 't'], 6 ['r', 'r', 'e'], 7 ['t', 'o', 'n'] ], 8 9 [ ['o','a','a'], 10 ['e','t','a'], 11 ['i','h','k']], 12 13 [ ['a','b','i'], 14 ['e','g','a'], 15 ['r','r','o'] ], 16 17 [ ['m','o','q'], 18 ['e','l','z'], 19 ['z','r','o'] ] ] 20 21 dictionaries = [["cat", "cater", "cartoon", "toon", "moon", "not", "tone", "apple", "ton", "art"], 22 ["oath","pea","ate","the", "iot"], ["ago", "ego", "bear", "gear", "rear", "big", "roar", "rig", "bar"], ["zoo", "zoom","zoz"]] 23 24 for i in range(len(grids)): 25 print("字符网格") 26 for row in grids[i]: 27 print(row) 28 29 # 使用子串去除尾部逗号 30 print("\n字典:", print_list(dictionaries[i])) 31 32 b = Boggle(grids[i], dictionaries[i]) 33 words = b.find_all_words() 34 35 print("输出:\t", print_words(words)) 36 print("--------------------------------------------------------------------------------------------------") 37 38if __name__ == '__main__': 39 main()
JS
1import {Boggle} from './Boggle.js'; 2import {printWords, printArray, printDictionary} from './PrintingFunctions.js'; 3 4let grids = [[ ['c', 'a', 't'], 5 ['r', 'r', 'e'], 6 ['t', 'o', 'n'] ], 7 8 [ ['o','a','a'], 9 ['e','t','a'], 10 ['i','h','k']], 11 12 [ ['a','b','i'], 13 ['e','g','a'], 14 ['r','r','o'] ], 15 16 [ ['m','o','q'], 17 ['e','l','z'], 18 ['z','r','o'] ] ]; 19 20let dictionaries = [new Set(["cat", "cater", "cartoon", "toon", "moon", "not", "tone", "apple", "ton", "art"]), 21 new Set(["oath","pea","ate","the", "iot"]), 22 new Set(["ago", "ego", "bear", "gear", "rear", "big", "roar", "rig", "bar"]), 23 new Set(["zoo", "zoom","zoz"]) ] 24 25 26for(let i =0 ;i < grids.length; i++){ 27 28 console.log("字符网格"); 29 for(let row of grids[i]){ 30 console.log(row); 31 } 32 let dictionaryPrint = printDictionary(dictionaries[i]); 33 console.log(); 34 35 console.log("字典:", printArray((dictionaryPrint))); 36 let b = new Boggle(grids[i], dictionaries[i]); 37 let words = b.findAllWords(); 38 39 let printOutput = printDictionary(words); 40 console.log("输出:\t" + printWords(printOutput)); 41 console.log("---------------------------------------------------------------------------------------------------------\n"); 42}
Ruby
1require './boggle' 2require './printing_functions' 3 4grids = [[['c', 'a', 't'], 5 ['r', 'r', 'e'], 6 ['t', 'o', 'n']], 7 8 [['o', 'a', 'a'], 9 ['e', 't', 'a'], 10 ['i', 'h', 'k']], 11 12 [['a', 'b','i'], 13 ['e', 'g','a'], 14 ['r', 'r','o']], 15 16 [['m', 'o','q'], 17 ['e', 'l','z'], 18 ['z', 'r','o']], 19 20 [["a"]], 21 22 [["f","e"],["a", "t"]], 23 24 [["v","a", "n", "e"],["h","c", "c", "f"],["a","n", "o", "a"],["t","n", "w", "n"]]] 25 26dictionaries = [["cat", "cater", "cartoon", "toon", "moon", "not", "tone", "apple", "ton", "art"], 27 ["oath","pea","ate","the", "iot"], 28 ["ago", "ego", "bear", "gear", "rear", "big", "roar", "rig", "bar"], 29 ["zoo", "zoom","zoz"], 30 ["a"], 31 ["eat", "fat"], 32 ["cat", "van", "hat", "can", "fan", "cow"]] 33 34 35 36grids.length.times do |i| 37 puts "字符网格:" 38 print_grid(grids[i]) 39 print "\n字典: " 40 print_dictionary(dictionaries[i]) 41 words = Boggle.new(grids[i], dictionaries[i]).find_all_words() 42 print "\n输出: " 43 print_words(words) 44 puts "\n---------------------------------------------------------------------------------------------------------\n\n" 45end
Go
1package main 2 3import ( 4 "fmt" 5) 6 7func main() { 8 9 grids := [][][]string{ 10 { 11 []string{"c", "a", "t"}, 12 []string{"r", "r", "e"}, 13 []string{"t", "o", "n"}, 14 }, 15 16 { 17 []string{"o", "a", "a"}, 18 []string{"e", "t", "a"}, 19 []string{"i", "h", "k"}, 20 }, 21 22 { 23 []string{"a", "b", "i"}, 24 []string{"e", "g", "a"}, 25 []string{"r", "r", "o"}, 26 }, 27 28 { 29 []string{"m", "o", "q"}, 30 []string{"e", "l", "z"}, 31 []string{"z", "r", "o"}, 32 }, 33 // { 34 // []string{"f","e"}, 35 // []string{"a","o"}, 36 // []string{"t","a"}, 37 // }, 38 } 39 40 dictionaries := [][]string{ 41 {"cat", "cater", "cartoon", "toon", "moon", "not", "tone", "apple", "ton", "art"}, 42 {"oath", "pea", "ate", "the", "iot"}, 43 {"ago", "ego", "bear", "gear", "rear", "big", "roar", "rig", "bar"}, 44 {"zoo", "zoom", "zoz"}, 45 //{"ate", "eat", "fat"}, 46 } 47 48 for i, grid := range grids { 49 fmt.Print("字符网格\n") 50 for row, _ := range grid { 51 // 自定义函数打印网格 52 PrintGrid(grid[row]) 53 } 54 // 自定义函数将字典转换为字符串 55 fmt.Printf("\n字典: %s\n", PrintDict(dictionaries[i])) 56 57 words := BoggleInit(grid, dictionaries[i]).FindAllWords() 58 // 自定义函数将列表集转换为字符串 59 fmt.Printf("输出:\t%s\n", PrintList(words)) 60 fmt.Printf("--------------------------------------------------------------------------------------------------\n") 61 } 62}
时间复杂度
该解决方案的时间复杂度为指数级，，其中 是网格的维度。
注意：计算时间复杂度所用的递推关系为：
空间复杂度
该解决方案的空间复杂度为平方级，，其中 是网格的维度。
注意：递归解法也会消耗栈空间。