【回溯 字典树（前缀树）】212. 单词搜索 II

2024-05-12 18:04
文章标签 搜索 单词 ii 字典 前缀 回溯 212

本文主要是介绍【回溯 字典树（前缀树）】212. 单词搜索 II，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

本文涉及知识点

回溯 字典树（前缀树）

LeetCode212. 单词搜索 II

给定一个 m x n 二维字符网格 board 和一个单词（字符串）列表 words， 返回所有二维网格上的单词 。
单词必须按照字母顺序，通过 相邻的单元格 内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母在一个单词中不允许被重复使用。
示例 1：
在这里插入图片描述

输入：board = [[“o”,“a”,“a”,“n”],[“e”,“t”,“a”,“e”],[“i”,“h”,“k”,“r”],[“i”,“f”,“l”,“v”]], words = [“oath”,“pea”,“eat”,“rain”]
输出：[“eat”,“oath”]
示例 2：
在这里插入图片描述

输入：board = [[“a”,“b”],[“c”,“d”]], words = [“abcb”]
输出：[]

提示：

m == board.length
n == board[i].length
1 <= m, n <= 12
board[i][j] 是一个小写英文字母
1 <= words.length <= 3 * 104
1 <= words[i].length <= 10
words[i] 由小写英文字母组成
words 中的所有字符串互不相同

回溯

用字典树存储所有words。
枚举起点，时间复杂度O(nm)。
最长的words[i]，除去第一个字符后，最多9个字符。后续字符4个。故处理每个起点的时间复杂是O(9n)
总时间复杂度 ≈ \approx ≈ 3$\times$107 超时边缘。
回溯部分一定要反复优化。

代码

核心代码

struct CVec
{int r;int c;CVec operator*(const int len)const{return { r * len,c * len };}
};struct CPos
{	int r = 0, c = 0;CPos(int tr, int tc) {r = tr;c = tc;}int ToMask()const { return s_MaxC * r + c; };bool operator==(const CPos& o)const{return (r == o.r) && (c == o.c);}CPos operator+(const CVec& v)const{return { r + v.r, c + v.c };}CPos operator-(const CVec& v)const{return{ r - v.r, c - v.c };}CVec operator-(const CPos& o)const{return {r - o.r,c- o.c};}inline static  int s_MaxC = 10'000;
};struct SPosHash {// 哈希函数的操作符重载，接受一个指针作为参数size_t operator()(const CPos& pos) const {// 简单的哈希函数示例，将指针地址转换为哈希值return (long long)100'000 * pos.r + pos.c;;}
};class CRange
{
public:CRange(int rCount, int cCount, std::function<bool(int, int)> funVilidCur):m_r(rCount),m_c(cCount), m_funVilidCur(funVilidCur){}bool Vilid(CPos pos)const{return (pos.r >= 0) && (pos.r < m_r) && (pos.c >= 0) && (pos.c < m_c) && m_funVilidCur(pos.r, pos.c);}const int m_r, m_c;
protected:std::function<bool(int, int)> m_funVilidCur;
};template<class TData = char, int iTypeNum = 26, TData cBegin = 'a'>
class CTrieNode
{
public:CTrieNode* AddChar(TData ele, int& iMaxID){
#ifdef _DEBUGif ((ele < cBegin) || (ele >= cBegin + iTypeNum)){return nullptr;}
#endifconst int index = ele - cBegin;auto ptr = m_vPChilds[ele - cBegin];if (!ptr){m_vPChilds[index] = new CTrieNode();
#ifdef _DEBUGm_vPChilds[index]->m_iID = ++iMaxID;m_childForDebug[ele] = m_vPChilds[index];
#endif}return m_vPChilds[index];}CTrieNode* GetChild(TData ele)const{
#ifdef _DEBUGif ((ele < cBegin) || (ele >= cBegin + iTypeNum)){return nullptr;}
#endifreturn m_vPChilds[ele - cBegin];}
protected:
#ifdef _DEBUGint m_iID = -1;std::unordered_map<TData, CTrieNode*> m_childForDebug;
#endif
public:int m_iLeafIndex = -1;
protected:CTrieNode* m_vPChilds[iTypeNum] = { nullptr };
};template<class TData = char, int iTypeNum = 26, TData cBegin = 'a'>
class CTrie
{
public:int GetLeadCount(){return m_iLeafCount;}CTrieNode<TData, iTypeNum, cBegin>* AddA(CTrieNode<TData, iTypeNum, cBegin>* par,TData curValue){auto curNode =par->AddChar(curValue, m_iMaxID);FreshLeafIndex(curNode);return curNode;}template<class IT>int Add(IT begin, IT end){auto pNode = &m_root;for (; begin != end; ++begin){pNode = pNode->AddChar(*begin, m_iMaxID);}FreshLeafIndex(pNode);return pNode->m_iLeafIndex;}	template<class IT>CTrieNode<TData, iTypeNum, cBegin>* Search(IT begin, IT end){auto ptr = &m_root;for (; begin != end; ++begin){ptr = ptr->GetChild(*begin);if (nullptr == ptr){return nullptr;}}return ptr;}CTrieNode<TData, iTypeNum, cBegin> m_root;
protected:void FreshLeafIndex(CTrieNode<TData, iTypeNum, cBegin>* pNode){if (-1 == pNode->m_iLeafIndex){pNode->m_iLeafIndex = m_iLeafCount++;}}int m_iMaxID = 0;int m_iLeafCount = 0;
};class Solution {
public:vector<string> findWords(vector<vector<char>>& board, vector<string>& words) {const int R = board.size();const int C = board[0].size();for (const auto& s : words) {m_trie.Add(s.begin(), s.end());}		vector<bool> vHas(m_trie.GetLeadCount());int hasVisit[12][12] ;memset(hasVisit, 0, sizeof(hasVisit));CRange rang(R, C, [&](int r, int c) {return !hasVisit[r][c]; });int move[][2] = { {0,1},{0,-1},{1,0},{-1,0}};std::function<void(CTrieNode<>* par, int r, int c)> BackTrack = [&](CTrieNode<>* par, int r, int c){auto p = par->GetChild(board[r][c]);if (nullptr == p) { return; }if (-1 != p->m_iLeafIndex) {vHas[p->m_iLeafIndex] = true;}hasVisit[r][c]=true;for (int i = 0; i < 4; i++) {const int r1 = r + move[i][0];const int c1 = c + move[i][1];if(!rang.Vilid(CPos(r1,c1 ))){continue;}BackTrack(p, r1, c1);}hasVisit[r][c] = false;};for (int r = 0; r < R; r++) {for (int c = 0; c < C; c++) {BackTrack(&m_trie.m_root, r, c);}}vector<string> vRet;for (const auto& s : words) {auto p = m_trie.Search(s.begin(), s.end());if (vHas[p->m_iLeafIndex]) {vRet.emplace_back(s);}}return vRet;}	CTrie<> m_trie;
};

测试用例

template<class T>
void Assert(const vector<T>& v1, const vector<T>& v2)
{if (v1.size() != v2.size()){assert(false);return;}for (int i = 0; i < v1.size(); i++){assert(v1[i] == v2[i]);}
}template<class T>
void Assert(const T& t1, const T& t2)
{assert(t1 == t2);
}int main()
{vector<vector<char>> board;vector<string> words;{Solution slu;board= { {'o','a','a','n'},{'e','t','a','e'},{'i','h','k','r'},{'i','f','l','v'} },words= { "oath","pea","eat","rain" };auto res = slu.findWords(board, words);Assert({ "oath","eat" }, res);}{Solution slu;board = { {'a','b'},{'c','d'} }, words = { "abcb" };auto res = slu.findWords(board, words);Assert({  }, res);}	}

2023年4月版

class Solution {
public:vector<string> findWords(vector<vector<char>>& board, vector<string>& words) {m_r = board.size();m_c = board[0].size();m_iMaskNum = m_r*m_c;m_vMove.resize(m_iMaskNum);for (int r = 0; r < m_r; r++){for (int c = 0; c < m_c; c++){int iMask = m_c*r + c;if (r > 0){m_vMove[iMask].emplace_back(iMask - m_c);}if (r + 1 < m_r){m_vMove[iMask].emplace_back(iMask + m_c);}if ( c > 0 ){m_vMove[iMask].emplace_back(iMask - 1);}if (c + 1 < m_c){m_vMove[iMask].emplace_back(iMask + 1);}}}for (const auto& s : words){long long llRet = 0;for (const auto& ch : s){llRet = llRet * 27 + ch - 'a'+1;m_setNeedSub.emplace(llRet);}m_setNeed.emplace(llRet);}int v[12] = { 0 };bool bPre[12 * 12] = { 0 };for (int i = 0; i < m_iMaskNum; i++){			const char& ch = board[i / m_c][i%m_c];v[0] = i;bPre[i] = true;dfs(v, 1,bPre, ch - 'a' + 1, board);bPre[i] = false;}vector<string> vRet;for (const auto& s : words){const long long llMask = Mask(s);if (!m_setNeed.count(llMask)){vRet.emplace_back(s);}}return vRet;}void dfs(int* v,int iSize, bool* vPre, const long long llMask, vector<vector<char>>& board){if (iSize > 10){return;}if (m_setNeed.count(llMask)){m_setNeed.erase(llMask);auto tmp = llMask;while (tmp > 0){auto it = m_setNeedSub.find(tmp);m_setNeedSub.erase(it);tmp /= 27;}}if (!m_setNeedSub.count(llMask)){return;}//const int iSize = v.size();const int iCur = v[iSize-1];for (const auto& next : m_vMove[iCur]){if (vPre[next]){continue;}v[iSize] = next;vPre[next] = true;dfs(v, iSize+1,vPre, llMask * 27 + board[next / m_c][next%m_c] - 'a' + 1, board);vPre[next] = false;}}long long Mask(const std::string& str){long long llRet = 0;for (const auto& ch : str){llRet = llRet * 27 + ch - 'a'+1;}return llRet;}int m_r, m_c;int m_iMaskNum;vector<vector<int>> m_vMove;std::unordered_multiset<long long> m_setNeedSub;std::unordered_set<long long> m_setNeed;
};

扩展阅读

视频课程

有效学习：明确的目标 及时的反馈 拉伸区（难度合适），可以先学简单的课程，请移步CSDN学院，听白银讲师（也就是鄙人）的讲解。
https://edu.csdn.net/course/detail/38771

如何你想快速形成战斗了，为老板分忧，请学习C#入职培训、C++入职培训等课程
https://edu.csdn.net/lecturer/6176

相关下载

想高屋建瓴的学习算法，请下载《喜缺全书算法册》doc版
https://download.csdn.net/download/he_zhidan/88348653

我想对大家说的话
《喜缺全书算法册》以原理、正确性证明、总结为主。
闻缺陷则喜是一个美好的愿望，早发现问题，早修改问题，给老板节约钱。
子墨子言之：事无终始，无务多业。也就是我们常说的专业的人做专业的事。
如果程序是一条龙，那算法就是他的是睛

测试环境

操作系统：win7 开发环境： VS2019 C++17
或者 操作系统：win10 开发环境： VS2022 C++17
如无特殊说明，本算法用**C++**实现。

这篇关于【回溯 字典树（前缀树）】212. 单词搜索 II的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/983340。

相关文章

认识、理解、分类——acm之搜索

认识、理解、分类——acm之搜索

普通搜索方法有两种：1、广度优先搜索；2、深度优先搜索； 更多搜索方法： 3、双向广度优先搜索； 4、启发式搜索（包括A*算法等）； 搜索通常会用到的知识点：状态压缩（位压缩，利用hash思想压缩）。
阅读更多...
hdu1240、hdu1253（三维搜索题）

hdu1240、hdu1253（三维搜索题）

1、从后往前输入，（x，y，z）; 2、从下往上输入，（y , z, x）; 3、从左往右输入，（z，x，y）； hdu1240代码如下： #include<iostream>#include<algorithm>#include<string>#include<stack>#include<queue>#include<map>#include<stdio.h>#inc
阅读更多...
hdu 4517 floyd+记忆化搜索

hdu 4517 floyd+记忆化搜索

题意： 有n（100）个景点，m（1000）条路，时间限制为t（300），起点s，终点e。 访问每个景点需要时间cost_i，每个景点的访问价值为value_i。 点与点之间行走需要花费的时间为g[ i ] [ j ] 。注意点间可能有多条边。 走到一个点时可以选择访问或者不访问，并且当前点的访问价值应该严格大于前一个访问的点。 现在求，从起点出发，到达终点，在时间限制内，能得到的最大
阅读更多...
AI基础 L9 Local Search II 局部搜索

AI基础 L9 Local Search II 局部搜索

Local Beam search 对于当前的所有k个状态，生成它们的所有可能后继状态。 检查生成的后继状态中是否有任何状态是解决方案。 如果所有后继状态都不是解决方案，则从所有后继状态中选择k个最佳状态。 当达到预设的迭代次数或满足某个终止条件时，算法停止。 — Choose k successors randomly, biased towards good ones — Close
阅读更多...
hdu4277搜索

hdu4277搜索

给你n个有长度的线段，问如果用上所有的线段来拼1个三角形，最多能拼出多少种不同的？ import java.io.BufferedInputStream;import java.io.BufferedReader;import java.io.IOException;import java.io.InputStream;import java.io.InputStreamReader;
阅读更多...
从0到1，AI我来了- （7）AI应用-ComfyUI-II（进阶）

从0到1，AI我来了- （7）AI应用-ComfyUI-II（进阶）

上篇comfyUI 入门 ，了解了TA是个啥，这篇，我们通过ComfyUI 及其相关Lora 模型，生成一些更惊艳的图片。这篇主要了解这些内容：         1、哪里获取模型？         2、实践如何画一个美女？         3、附录：               1）相关SD(稳定扩散模型的组成部分）               2）模型放置目录（重要）
阅读更多...
POJ2001字典树

POJ2001字典树

给出n个单词，求出每个单词的非公共前缀，如果没有，则输出自己。 import java.io.BufferedReader;import java.io.InputStream;import java.io.InputStreamReader;import java.io.PrintWriter;import java.io.UnsupportedEncodingException;
阅读更多...
学习记录：js算法（二十八）：删除排序链表中的重复元素、删除排序链表中的重复元素II

学习记录：js算法（二十八）：删除排序链表中的重复元素、删除排序链表中的重复元素II

文章目录 删除排序链表中的重复元素我的思路解法一：循环解法二：递归 网上思路 删除排序链表中的重复元素 II我的思路网上思路 总结 删除排序链表中的重复元素 给定一个已排序的链表的头 head ， 删除所有重复的元素，使每个元素只出现一次 。返回 已排序的链表 。 图一 图二 示例 1：（图一）输入：head = [1,1,2]输出：[1,2]示例 2：（图
阅读更多...
每日一练7：简写单词（含链接）

每日一练7：简写单词（含链接）

1.链接 简写单词_牛客题霸_牛客网 2.题目 3.代码1（错误经验） #include <iostream>#include <string>using namespace std;int main() {string s;string ret;int count = 0;while(cin >> s)for(auto a : s){if(count == 0){if( a <=
阅读更多...
回溯——9.全排列

回溯——9.全排列

力扣题目链接 给定一个 没有重复 数字的序列，返回其所有可能的全排列。 示例: 输入: [1,2,3]输出: [ [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1] ] 解题思路 问题建模：题目要求给出一个数组的所有排列组合，属于典型的全排列问题，这可以用回溯法来解决。回溯法通过递归的方式，依次将数组中的每个元素放入排列中，直到生成
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2