第 483 场周赛Q2——3799. 单词方块 II

题目链接：3799. 单词方块 II（中等）

算法原理：

解法：暴力枚举 + 约束过滤

21ms击败70.07%

时间复杂度O(N⁴ log N)

①数据预处理：将所有单词存入 HashSet，快速校验单词存在性
②暴力枚举候选：通过四重嵌套循环，分别遍历作为四方块 “上、左、右、下” 四个方向的单词
③唯一性过滤：要求 top、left、right、bottom 四个单词互不相同，过滤重复组合
④字符边界约束：校验四方块的字符匹配规则（索引从 0 开始）：
上边首字符 = 左边首字符（top [0] == left [0]）；
上边尾字符 = 右边首字符（top [3] == right [0]）；
下边首字符 = 左边尾字符（bottom [0] == left [3]）；
下边尾字符 = 右边尾字符（bottom [3] == right [3]）
⑤结果收集与排序：将满足约束的四单词组合存入结果列表，最后按列表内单词依次字典序排序结果

Java代码：

class Solution { public List<List<String>> wordSquares(String[] words) { //存储单词，方便快速检查存在性 Set<String> wordSet=new HashSet<>(); //手动把word数组的元素添加到Set里 for(String word:words) wordSet.add(word); List<List<String>> ret=new ArrayList<>(); //遍历所有可能的top、left、right、bottom组合 for(String top:words){ for(String left:words){ //确保top和left不同 if(top.equals(left)) continue; //检查约束：top[0]==left[0] if(top.charAt(0)!=left.charAt(0)) continue; for(String right:words){ //确保right与top、left都不同 if(top.equals(right)||right.equals(left)) continue; //检查约束：top[3]==right[0] if(top.charAt(3)!=right.charAt(0)) continue; //确定bottom需要满足的首字符和尾字符 char bottomFirst=left.charAt(3); char bottomLast=right.charAt(3); for(String bottom:words){ //确保bottom与top、left、right都不同 if(bottom.equals(top)||bottom.equals(left)||bottom.equals(right)) continue; //检查约束：bottom[0]==left[3]且bottom[3]==right[3] if(bottom.charAt(0)==bottomFirst&&bottom.charAt(3)==bottomLast){ //手动创建List并添加四个单词 List<String> q=new ArrayList<>(); q.add(top);q.add(left);q.add(right);q.add(bottom); ret.add(q); } } } } } //比较规则，在上左右下的框架下，从每组的首单词一次开始往后按字典学比较排序 Collections.sort(ret,new Comparator<List<String>>(){ @Override public int compare(List<String> a,List<String> b){ for(int i=0;i<4;i++){ int cmp=a.get(i).compareTo(b.get(i)); if(cmp!=0) return cmp; } return 0; } }); return ret; } }