Medium

题目描述

给定一个字符串数组 words，由不同的 4 个字母组成的字符串组成，每个字符串只包含小写英文字母。

一个单词方格由 4 个不同的单词组成：top、left、right 和 bottom，排列如下：

  • top 构成顶行
  • bottom 构成底行
  • left 构成左列（从上到下）
  • right 构成右列（从上到下）

必须满足以下条件：

  • top[0] == left[0]，top[3] == right[0]
  • bottom[0] == left[3]，bottom[3] == right[3]

返回所有有效的不同单词方格，按 4 元组 (top, left, right, bottom) 的字典序升序排列。

示例 1:

输入: words = ["able","area","echo","also"]
输出: [["able","area","echo","also"],["area","able","also","echo"]]

示例 2:

输入: words = ["code","cafe","eden","edge"]
输出: []

约束:

  • 4 <= words.length <= 15
  • words[i].length == 4
  • words[i] 只包含小写英文字母
  • 所有 words[i] 都不同

解题思路

这道题需要找出所有满足条件的 4 个单词组成的方格。根据题目描述，我们需要找到 4 个不同的单词作为 top、left、right、bottom，使得四个角的字符满足约束条件。

思路分析：

  1. 暴力枚举：由于单词数量最多 15 个，我们可以使用四层循环枚举所有可能的 4 个单词组合
  2. 约束检查：对于每个组合，检查是否满足四个角的约束条件
  3. 去重和排序：使用 set 去重，最后转换为排序的结果

具体步骤：

  • 枚举所有可能的 (top, left, right, bottom) 组合
  • 检查约束条件：top[0] == left[0]、top[3] == right[0]、bottom[0] == left[3]、bottom[3] == right[3]
  • 将满足条件的组合加入结果集
  • 由于要求字典序排序，我们可以使用 set 自动排序并去重

时间复杂度为 O(n⁴)，其中 n 是单词数量。虽然看起来复杂度较高，但由于 n ≤ 15，实际运行时间是可接受的。

代码实现

class Solution {
public:
    vector<vector<string>> wordSquares(vector<string>& words) {
        set<vector<string>> result;
        int n = words.size();
        
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (i == j) continue;
                for (int k = 0; k < n; k++) {
                    if (k == i || k == j) continue;
                    for (int l = 0; l < n; l++) {
                        if (l == i || l == j || l == k) continue;
                        
                        string top = words[i];
                        string left = words[j];
                        string right = words[k];
                        string bottom = words[l];
                        
                        if (top[0] == left[0] && top[3] == right[0] &&
                            bottom[0] == left[3] && bottom[3] == right[3]) {
                            result.insert({top, left, right, bottom});
                        }
                    }
                }
            }
        }
        
        return vector<vector<string>>(result.begin(), result.end());
    }
};

class Solution:
    def wordSquares(self, words: List[str]) -> List[List[str]]:
        result = set()
        n = len(words)
        
        for i in range(n):
            for j in range(n):
                if i == j:
                    continue
                for k in range(n):
                    if k == i or k == j:
                        continue
                    for l in range(n):
                        if l == i or l == j or l == k:
                            continue
                        
                        top, left, right, bottom = words[i], words[j], words[k], words[l]
                        
                        if (top[0] == left[0] and top[3] == right[0] and
                            bottom[0] == left[3] and bottom[3] == right[3]):
                            result.add((top, left, right, bottom))
        
        return sorted(list(result))

public class Solution {
    public IList<IList<string>> WordSquares(string[] words) {
        var result = new SortedSet<string>(StringComparer.Ordinal);
        int n = words.Length;
        
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (i == j) continue;
                for (int k = 0; k < n; k++) {
                    if (k == i || k == j) continue;
                    for (int l = 0; l < n; l++) {
                        if (l == i || l == j || l == k) continue;
                        
                        string top = words[i];
                        string left = words[j];
                        string right = words[k];
                        string bottom = words[l];
                        
                        if (top[0] == left[0] && top[3] == right[0] &&
                            bottom[0] == left[3] && bottom[3] == right[3]) {
                            string key = $"{top},{left},{right},{bottom}";
                            result.Add(key);
                        }
                    }
                }
            }
        }
        
        var finalResult = new List<IList<string>>();
        foreach (string s in result) {
            var parts = s.Split(',');
            finalResult.Add(new List<string> { parts[0], parts[1], parts[2], parts[3] });
        }
        
        return finalResult;
    }
}

var wordSquares = function(words) {
    const result = [];
    const n = words.length;
    
    for (let i = 0; i < n; i++) {
        for (let j = 0; j < n; j++) {
            if (i === j) continue;
            for (let k = 0; k < n; k++) {
                if (k === i || k === j) continue;
                for (let l = 0; l < n; l++) {
                    if (l === i || l === j || l === k) continue;
                    
                    const top = words[i];
                    const left = words[j];
                    const right = words[k];
                    const bottom = words[l];
                    
                    if (top[0] === left[0] && 
                        top[3] === right[0] && 
                        bottom[0] === left[3] && 
                        bottom[3] === right[3]) {
                        result.push([top, left, right, bottom]);
                    }
                }
            }
        }
    }
    
    result.sort((a, b) => {
        for (let i = 0; i < 4; i++) {
            if (a[i] < b[i]) return -1;
            if (a[i] > b[i]) return 1;
        }
        return 0;
    });
    
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n⁴)四层循环遍历所有可能的单词组合，每次检查约束条件为 O(1)
空间复杂度O(k)k 为满足条件的方格数量，用于存储结果