Word squares ii

Array String Backtracking Sorting Enumeration

54.9% acceptance

Mar 15, 2026

You are given a string array words, consisting of distinct 4-letter strings. A word square consists of 4 distinct words: top, left, right, bottom arranged so that: top[0] == left[0], top[3] == right[0], bottom[0] == left[3], bottom[3] == right[3] Return all valid distinct word squares sorted lexicographically by (top, left, right, bottom).

Solution

Rust

Time O(n³)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn word_squares(words: Vec<String>) -> Vec<Vec<String>> {
    let n = words.len();
    let w: Vec<&[u8]> = words.iter().map(|s| s.as_bytes()).collect();
    let mut result = Vec::new();
    for top in 0..n {
      for left in 0..n {
        if left == top { continue; }
        if w[top][0] != w[left][0] { continue; }
        for right in 0..n {
          if right == top || right == left { continue; }
          if w[top][3] != w[right][0] { continue; }
          for bottom in 0..n {
            if bottom == top || bottom == left || bottom == right { continue; }
            if w[bottom][0] != w[left][3] { continue; }
            if w[bottom][3] != w[right][3] { continue; }
            result.push(vec![
              words[top].clone(),
              words[left].clone(),
              words[right].clone(),
              words[bottom].clone(),
            ]);
          }
        }
      }
    }
    result.sort();
    result
  }
}