Skip to content

3799. Word Squares II

Description

You are given a string array words, consisting of distinct 4-letter strings, each containing lowercase English letters.

A word square consists of 4 distinct words: top, left, right and bottom, arranged as follows:

  • top forms the top row.
  • bottom forms the bottom row.
  • left forms the left column (top to bottom).
  • right forms the right column (top to bottom).

It must satisfy:

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

Return all valid distinct word squares, sorted in ascending lexicographic order by the 4-tuple (top, left, right, bottom)​​​​​​​.

 

Example 1:

Input: words = ["able","area","echo","also"]

Output: [["able","area","echo","also"],["area","able","also","echo"]]

Explanation:

There are exactly two valid 4-word squares that satisfy all corner constraints:

  • "able" (top), "area" (left), "echo" (right), "also" (bottom)
    • top[0] == left[0] == 'a'
    • top[3] == right[0] == 'e'
    • bottom[0] == left[3] == 'a'
    • bottom[3] == right[3] == 'o'
  • "area" (top), "able" (left), "also" (right), "echo" (bottom)
    • All corner constraints are satisfied.

Thus, the answer is [["able","area","echo","also"],["area","able","also","echo"]].

Example 2:

Input: words = ["code","cafe","eden","edge"]

Output: []

Explanation:

No combination of four words satisfies all four corner constraints. Thus, the answer is empty array [].

 

Constraints:

  • 4 <= words.length <= 15
  • words[i].length == 4
  • words[i] consists of only lowercase English letters.
  • All words[i] are distinct.

Solutions

Solution 1

Thinking

The words are distinct \(4\)-letter strings and there are at most \(15\) of them, so we may enumerate four distinct indices. After sorting, four nested loops pick \(\textit{top},\textit{left},\textit{right},\textit{bottom}\) and keep a tuple when the four corner letters match.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution:
    def wordSquares(self, words: List[str]) -> List[List[str]]:
        words.sort()
        n = len(words)
        ans = []
        for i in range(n):
            top = words[i]
            for j in range(n):
                if j != i:
                    left = words[j]
                    for k in range(n):
                        if k != j and k != i:
                            right = words[k]
                            for h in range(n):
                                if h != k and h != j and h != i:
                                    bottom = words[h]
                                    if (
                                        top[0] == left[0]
                                        and top[3] == right[0]
                                        and bottom[0] == left[3]
                                        and bottom[3] == right[3]
                                    ):
                                        ans.append([top, left, right, bottom])
        return ans

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution {
    public List<List<String>> wordSquares(String[] words) {
        Arrays.sort(words);
        int n = words.length;
        List<List<String>> ans = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            String top = words[i];
            for (int j = 0; j < n; j++) {
                if (j != i) {
                    String left = words[j];
                    for (int k = 0; k < n; k++) {
                        if (k != j && k != i) {
                            String right = words[k];
                            for (int h = 0; h < n; h++) {
                                if (h != k && h != j && h != i) {
                                    String bottom = words[h];
                                    if (top.charAt(0) == left.charAt(0)
                                        && top.charAt(3) == right.charAt(0)
                                        && bottom.charAt(0) == left.charAt(3)
                                        && bottom.charAt(3) == right.charAt(3)) {
                                        ans.add(List.of(top, left, right, bottom));
                                    }
                                }
                            }
                        }
                    }
                }
            }
        }
        return ans;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class Solution {
public:
    vector<vector<string>> wordSquares(vector<string>& words) {
        ranges::sort(words);
        int n = words.size();
        vector<vector<string>> ans;

        for (int i = 0; i < n; i++) {
            string top = words[i];
            for (int j = 0; j < n; j++) {
                if (j != i) {
                    string left = words[j];
                    for (int k = 0; k < n; k++) {
                        if (k != j && k != i) {
                            string right = words[k];
                            for (int h = 0; h < n; h++) {
                                if (h != k && h != j && h != i) {
                                    string bottom = words[h];
                                    if (top[0] == left[0] && top[3] == right[0] && bottom[0] == left[3] && bottom[3] == right[3]) {
                                        ans.push_back({top, left, right, bottom});
                                    }
                                }
                            }
                        }
                    }
                }
            }
        }
        return ans;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
func wordSquares(words []string) [][]string {
    sort.Strings(words)
    n := len(words)
    ans := [][]string{}

    for i := 0; i < n; i++ {
        top := words[i]
        for j := 0; j < n; j++ {
            if j != i {
                left := words[j]
                for k := 0; k < n; k++ {
                    if k != j && k != i {
                        right := words[k]
                        for h := 0; h < n; h++ {
                            if h != k && h != j && h != i {
                                bottom := words[h]
                                if top[0] == left[0] &&
                                    top[3] == right[0] &&
                                    bottom[0] == left[3] &&
                                    bottom[3] == right[3] {
                                    ans = append(ans, []string{top, left, right, bottom})
                                }
                            }
                        }
                    }
                }
            }
        }
    }
    return ans
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
function wordSquares(words: string[]): string[][] {
    words.sort();
    const n = words.length;
    const ans: string[][] = [];

    for (let i = 0; i < n; i++) {
        const top = words[i];
        for (let j = 0; j < n; j++) {
            if (j !== i) {
                const left = words[j];
                for (let k = 0; k < n; k++) {
                    if (k !== j && k !== i) {
                        const right = words[k];
                        for (let h = 0; h < n; h++) {
                            if (h !== k && h !== j && h !== i) {
                                const bottom = words[h];
                                if (
                                    top[0] === left[0] &&
                                    top[3] === right[0] &&
                                    bottom[0] === left[3] &&
                                    bottom[3] === right[3]
                                ) {
                                    ans.push([top, left, right, bottom]);
                                }
                            }
                        }
                    }
                }
            }
        }
    }

    return ans;
}

Comments