The power of pruning in backtracking VI

Backtracking is a powerful strategy, and yes if can become exponential even with pruning, but remember that exponential might still be acceptable depending on the size of the input. For instance, in this case there isn't a lot of pruning and the solution ends up being N^4, but N = 15 in this case which is about 50K iterations which is for all practical purposes a "linear" solution. Code is down below, cheers, ACC.

Word Squares II - LeetCode

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.

public class Solution {
    public IList> WordSquares(string[] words)
    {
        SortedSet[] sortedWords = new SortedSet[26];

        for (int i = 0; i < sortedWords.Length; i++)
            sortedWords[i] = new SortedSet();

        foreach(string word in words)
        {
            int index = (int)(word[0] - 'a');
            sortedWords[index].Add(word);
        }

        string[] square = new string[4];
        List> retVal = new List>();

        ProcessWordSquare(square, 0, sortedWords, 0, ref retVal);

        return retVal;
    }

    private void ProcessWordSquare(string[] square,
                                   int indexSquare /*0 top, 1 left, 2 right, 3 bottom*/,
                                   SortedSet[] sortedWords,
                                   int indexSortedWords,
                                   ref List> retVal)
    {
        if (indexSquare >= square.Length)
        {
            List list = new List();
            foreach (string w in square) list.Add(w);
            retVal.Add(list);
            return;
        }

        if (indexSortedWords >= sortedWords.Length) return;

        for (int i = indexSortedWords; i < sortedWords.Length; i++)
        {
            if (sortedWords[i].Count > 0)
            {
                foreach (string word in sortedWords[i])
                {
                    bool used = false;
                    for (int j = 0; j < indexSquare; j++)
                    {
                        if (square[j] == word)
                        {
                            used = true;
                            break;
                        }
                    }
                    if (used) continue;

                    if (indexSquare == 0)
                    {
                        square[indexSquare] = word;
                        ProcessWordSquare(square, indexSquare + 1, sortedWords, indexSortedWords, ref retVal);
                    }
                    else if (indexSquare == 1 && square[0][0] == word[0])
                    {
                        square[indexSquare] = word;
                        ProcessWordSquare(square, indexSquare + 1, sortedWords, indexSortedWords, ref retVal);
                    }
                    else if (indexSquare == 2 && square[0][3] == word[0])
                    {
                        square[indexSquare] = word;
                        ProcessWordSquare(square, indexSquare + 1, sortedWords, indexSortedWords, ref retVal);
                    }
                    else if (indexSquare == 3 && square[1][3] == word[0] && square[2][3] == word[3])
                    {
                        square[indexSquare] = word;
                        ProcessWordSquare(square, indexSquare + 1, sortedWords, indexSortedWords, ref retVal);
                    }
                }
            }
        }
    }
}