营销型网站建设主要教学内容,上海微网站制作,山东省青州市建设局网站,电子商务平台自身提供的数据工具文章目录1. 题目2. 解题1. 题目
给定一个单词集合 #xff08;没有重复#xff09;#xff0c;找出其中所有的 单词方块 。
一个单词序列形成了一个有效的单词方块的意思是指从第 k 行和第 k 列 (0 ≤ k max(行数, 列数)) 来看都是相同的字符串。
例如#xff0c;单…
文章目录1. 题目2. 解题1. 题目
给定一个单词集合 没有重复找出其中所有的 单词方块 。
一个单词序列形成了一个有效的单词方块的意思是指从第 k 行和第 k 列 (0 ≤ k max(行数, 列数)) 来看都是相同的字符串。
例如单词序列 [ball,area,lead,lady] 形成了一个单词方块因为每个单词从水平方向看和从竖直方向看都是相同的。
b a l l
a r e a
l e a d
l a d y注意
单词个数大于等于 1 且不超过 500。
所有的单词长度都相同。
单词长度大于等于 1 且不超过 5。
每个单词只包含小写英文字母 a-z。示例 1
输入
[area,lead,wall,lady,ball]
输出
[[ wall,area,lead,lady],[ ball,area,lead,lady]
]
解释
输出包含两个单词方块输出的顺序不重要
只需要保证每个单词方块内的单词顺序正确即可。 示例 2
输入
[abat,baba,atan,atal]
输出
[[ baba,abat,baba,atan],[ baba,abat,baba,atal]
]解释
输出包含两个单词方块输出的顺序不重要
只需要保证每个单词方块内的单词顺序正确即可。 来源力扣LeetCode 链接https://leetcode-cn.com/problems/word-squares 著作权归领扣网络所有。商业转载请联系官方授权非商业转载请注明出处。 2. 解题
类似题目程序员面试金典 - 面试题 17.25. 单词矩阵Trie树DFS回溯hard
trie 的每个节点记录经过该节点的单词下标
class trie
{
public:bool isEnd false;trie* next[26] {NULL};vectorint wd;//经过该节点的单词下标void insert(string s, int idx){trie *cur this;for(int i 0; i s.size(); i){if(!cur-next[s[i]-a])cur-next[s[i]-a] new trie();cur cur-next[s[i]-a];cur-wd.push_back(idx);}cur-isEnd true;}
};
class Solution {vectorvectorstring ans;int n;
public:vectorvectorstring wordSquares(vectorstring words) {trie* t new trie();for(int i 0; i words.size(); i)t-insert(words[i], i);n words[0].size();vectorstring mat;for(auto w : words){mat.push_back(w);//以每个单词为1第一行开始查找dfs(words, t, mat, 1);mat.pop_back();}return ans;}void dfs(vectorstring words, trie* t, vectorstring mat, int len){if(len n){ans.push_back(mat);return;}string nextprefix;//获取下一行的前缀for(int i 0; i len; i)nextprefix mat[i][len];trie* cur t;for(int i 0; i nextprefix.size(); i){ //在trie中检查前缀是否存在if(!cur-next[nextprefix[i]-a]) return;cur cur-next[nextprefix[i]-a];}for(int wd_idx : cur-wd){ //存在前缀在当前节点的单词中加入下一个单词mat.push_back(words[wd_idx]);dfs(words, t, mat, len1);mat.pop_back();}}
};160 ms 16.9 MB 我的CSDN博客地址 https://michael.blog.csdn.net/
长按或扫码关注我的公众号Michael阿明一起加油、一起学习进步
