本文涉及知识点
回溯 字典树（前缀树）
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 _DEBUG
if ((ele < cBegin) || (ele >= cBegin + iTypeNum))
{
return nullptr;
}
#endif
const int index = ele - cBegin;
auto ptr = m_vPChilds[ele - cBegin];
if (!ptr)
{
m_vPChilds[index] = new CTrieNode();
#ifdef _DEBUG
m_vPChilds[index]->m_iID = ++iMaxID;
m_childForDebug[ele] = m_vPChilds[index];
#endif
}
return m_vPChilds[index];
}
CTrieNode* GetChild(TData ele)const
{
#ifdef _DEBUG
if ((ele < cBegin) || (ele >= cBegin + iTypeNum))
{
return nullptr;
}
#endif
return m_vPChilds[ele - cBegin];
}
protected:
#ifdef _DEBUG
int 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++**实现。
