单词矩阵
难度:
标签:
题目描述
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 <= 1000words[i].length <= 100- It's guaranteed that all the words are randomly generated.
代码结果
运行时间: 528 ms, 内存: 17.1 MB
/*
* 思路：
* 1. 遍历所有单词，找出所有长度相同的单词组合。
* 2. 尝试将这些单词组合成矩形，验证每列是否也是一个单词。
* 3. 返回面积最大的矩形。
*/
import java.util.*;
import java.util.stream.Collectors;
public class MaxRectangleStream {
public List<String> maxRectangle(String[] words) {
Map<Integer, List<String>> map = Arrays.stream(words)
.collect(Collectors.groupingBy(String::length));
int[] maxArea = {0};
List<String> result = new ArrayList<>();
map.forEach((len, wordList) -> {
List<String> rectangle = findMaxRectangle(wordList);
int area = rectangle.size() * len;
if (area > maxArea[0]) {
maxArea[0] = area;
result = rectangle;
}
});
return result;
}
private List<String> findMaxRectangle(List<String> words) {
List<String> result = new ArrayList<>();
int maxArea = 0;
int n = words.size();
for (int i = 0; i < n; i++) {
List<String> temp = new ArrayList<>();
temp.add(words.get(i));
for (int j = i + 1; j < n; j++) {
temp.add(words.get(j));
if (isValidRectangle(temp)) {
int area = temp.size() * temp.get(0).length();
if (area > maxArea) {
maxArea = area;
result = new ArrayList<>(temp);
}
}
}
}
return result;
}
private boolean isValidRectangle(List<String> words) {
int m = words.size();
int n = words.get(0).length();
return IntStream.range(0, n)
.mapToObj(j -> words.stream()
.map(word -> word.charAt(j))
.collect(StringBuilder::new, StringBuilder::append, StringBuilder::append)
.toString())
.allMatch(words::contains);
}
public static void main(String[] args) {
MaxRectangleStream mr = new MaxRectangleStream();
String[] words = {"this", "real", "hard", "trh", "hea", "iar", "sld"};
List<String> result = mr.maxRectangle(words);
result.forEach(System.out::println);
}
}
解释
方法:
该题解采用了递归和回溯的方式来尝试构造符合条件的矩形。首先通过单词初始化将所有的单词按照长度、首字母和尾字母分类存储。接着从最长的单词开始尝试作为矩形的上边，并从单词的头尾字母出发向下递归，以此构造出可能的左边、右边和下边。构建过程中采用了剪枝策略，如果当前正在构建的矩形面积已经小于已知的最大矩形面积，则停止当前分支的进一步搜索。每次成功构造出一个矩形后，检查该矩形的所有行和列是否都是有效单词，并更新最大面积和最佳矩形结果。
时间复杂度:
O(n^L)（理论最坏情况）
空间复杂度:
O(n)
代码细节讲解
🦆
message
▷