Question

17.25. Word Rectangle

中文文档

Description

Given a list of millions of words, design an algorithm to create the largest possible rectangle of letters such that every row forms a word (reading left to right) and every column forms a word (reading top to bottom). The words need not be chosen consecutively from the list but all rows must be the same length and all columns must be the same height.

If there are more than one answer, return any one of them. A word can be used more than once.

Example 1:

Input: ["this", "real", "hard", "trh", "hea", "iar", "sld"]

Output:

[

  "this",

  "real",

  "hard"

]

Example 2:

Input: ["aa"]

Output: ["aa","aa"]

Notes:

• words.length <= 1000
• words[i].length <= 100
• It's guaranteed that all the words are randomly generated.

Solutions

Solution 1

class Trie:
  def __init__(self):
    self.children = [None] * 26
    self.is_end = False

  def insert(self, w):
    node = self
    for c in w:
      idx = ord(c) - ord("a")
      if node.children[idx] is None:
        node.children[idx] = Trie()
      node = node.children[idx]
    node.is_end = True


class Solution:
  def maxRectangle(self, words: List[str]) -> List[str]:
    def check(mat):
      m, n = len(mat), len(mat[0])
      ans = 1
      for j in range(n):
        node = trie
        for i in range(m):
          idx = ord(mat[i][j]) - ord("a")
          if node.children[idx] is None:
            return 0
          node = node.children[idx]
        if not node.is_end:
          ans = 2
      return ans

    def dfs(ws):
      nonlocal ans, max_s, max_l
      if len(ws[0]) * max_l <= max_s or len(t) >= max_l:
        return

      for w in ws:
        t.append(w)
        st = check(t)
        if st == 0:
          t.pop()
          continue
        if st == 1 and max_s < len(t) * len(t[0]):
          ans = t[:]
          max_s = len(t) * len(t[0])
        dfs(ws)
        t.pop()

    d = defaultdict(list)
    trie = Trie()
    max_l = 0
    for w in words:
      trie.insert(w)
      max_l = max(max_l, len(w))
      d[len(w)].append(w)

    max_s = 0
    ans = []
    for ws in d.values():
      t = []
      dfs(ws)
    return ans

class Trie {
  Trie[] children = new Trie[26];
  boolean isEnd;

  void insert(String word) {
    Trie node = this;
    for (char c : word.toCharArray()) {
      c -= 'a';
      if (node.children[c] == null) {
        node.children[c] = new Trie();
      }
      node = node.children[c];
    }
    node.isEnd = true;
  }
}

class Solution {
  private int maxL;
  private int maxS;
  private String[] ans;
  private Trie trie = new Trie();
  private List<String> t = new ArrayList<>();

  public String[] maxRectangle(String[] words) {
    Map<Integer, List<String>> d = new HashMap<>(100);
    for (String w : words) {
      maxL = Math.max(maxL, w.length());
      trie.insert(w);
      d.computeIfAbsent(w.length(), k -> new ArrayList<>()).add(w);
    }
    for (List<String> ws : d.values()) {
      t.clear();
      dfs(ws);
    }
    return ans;
  }

  private void dfs(List<String> ws) {
    if (ws.get(0).length() * maxL <= maxS || t.size() >= maxL) {
      return;
    }
    for (String w : ws) {
      t.add(w);
      int st = check(t);
      if (st == 0) {
        t.remove(t.size() - 1);
        continue;
      }
      if (st == 1 && maxS < t.size() * t.get(0).length()) {
        maxS = t.size() * t.get(0).length();
        ans = t.toArray(new String[0]);
      }
      dfs(ws);
      t.remove(t.size() - 1);
    }
  }

  private int check(List<String> mat) {
    int m = mat.size(), n = mat.get(0).length();
    int ans = 1;
    for (int j = 0; j < n; ++j) {
      Trie node = trie;
      for (int i = 0; i < m; ++i) {
        int idx = mat.get(i).charAt(j) - 'a';
        if (node.children[idx] == null) {
          return 0;
        }
        node = node.children[idx];
      }
      if (!node.isEnd) {
        ans = 2;
      }
    }
    return ans;
  }
}

class Trie {
public:
  vector<Trie*> children;
  bool is_end;

  Trie() {
    children = vector<Trie*>(26, nullptr);
    is_end = false;
  }

  void insert(const string& word) {
    Trie* cur = this;
    for (char c : word) {
      c -= 'a';
      if (cur->children[c] == nullptr) {
        cur->children[c] = new Trie;
      }
      cur = cur->children[c];
    }
    cur->is_end = true;
  }
};

class Solution {
public:
  vector<string> maxRectangle(vector<string>& words) {
    unordered_map<int, vector<string>> d;
    int maxL = 0, maxS = 0;
    vector<string> ans;
    vector<string> t;
    Trie* trie = new Trie();
    for (auto& w : words) {
      maxL = max(maxL, (int) w.size());
      d[w.size()].emplace_back(w);
      trie->insert(w);
    }
    auto check = [&](vector<string>& mat) {
      int m = mat.size(), n = mat[0].size();
      int ans = 1;
      for (int j = 0; j < n; ++j) {
        Trie* node = trie;
        for (int i = 0; i < m; ++i) {
          int idx = mat[i][j] - 'a';
          if (!node->children[idx]) {
            return 0;
          }
          node = node->children[idx];
        }
        if (!node->is_end) {
          ans = 2;
        }
      }
      return ans;
    };

    function<void(vector<string>&)> dfs = [&](vector<string>& ws) {
      if (ws[0].size() * maxL <= maxS || t.size() >= maxL) {
        return;
      }
      for (auto& w : ws) {
        t.emplace_back(w);
        int st = check(t);
        if (st == 0) {
          t.pop_back();
          continue;
        }
        if (st == 1 && maxS < t.size() * t[0].size()) {
          maxS = t.size() * t[0].size();
          ans = t;
        }
        dfs(ws);
        t.pop_back();
      }
    };
    for (auto& [_, ws] : d) {
      t.clear();
      dfs(ws);
    }
    return ans;
  }
};

type Trie struct {
  children [26]*Trie
  isEnd  bool
}

func newTrie() *Trie {
  return &Trie{}
}
func (this *Trie) insert(word string) {
  node := this
  for _, c := range word {
    c -= 'a'
    if node.children[c] == nil {
      node.children[c] = newTrie()
    }
    node = node.children[c]
  }
  node.isEnd = true
}

func maxRectangle(words []string) (ans []string) {
  trie := newTrie()
  d := map[int][]string{}
  t := []string{}
  var maxL, maxS int
  for _, w := range words {
    maxL = max(maxL, len(w))
    d[len(w)] = append(d[len(w)], w)
    trie.insert(w)
  }
  check := func(mat []string) int {
    m, n := len(mat), len(mat[0])
    ans := 1
    for j := 0; j < n; j++ {
      node := trie
      for i := 0; i < m; i++ {
        idx := mat[i][j] - 'a'
        if node.children[idx] == nil {
          return 0
        }
        node = node.children[idx]
      }
      if !node.isEnd {
        ans = 2
      }
    }
    return ans
  }
  var dfs func([]string)
  dfs = func(ws []string) {
    if len(ws[0])*maxL <= maxS || len(t) >= maxL {
      return
    }
    for _, w := range ws {
      t = append(t, w)
      st := check(t)
      if st == 0 {
        t = t[:len(t)-1]
        continue
      }
      if st == 1 && maxS < len(t)*len(t[0]) {
        maxS = len(t) * len(t[0])
        ans = append([]string{}, t...)
      }
      dfs(ws)
      t = t[:len(t)-1]
    }
  }
  for _, ws := range d {
    dfs(ws)
  }
  return
}