我在Leetcode上遇到了这个解决方案，它是针对不使用排序的组变形的。对于这个解决方案，我有两个问题。1.在将sArr转换为字符串的步骤中，我们要做什么-String test = Arrays.toString(sArr);我调试了一下，发现测试字符串是一个int数组，对于输入字符串中的每个字母，值都是1。例如，如果我的输入字符串是eat，这段代码的时间复杂度是O（m * n）-n，是内部for循环中每一个字符串的长度吗？如果是O（mn）-n，那么这个时间复杂度是O（mn）- n，这段代码的时间复杂度是O（m*n）- n，这段代码的时间复杂度是O（m * n）。
public List<List<String>> groupAnagrams(String[] strs) {
List<List<String>> output = new ArrayList();
if(strs == null) {
return output;
}
Map<String,List<String>> outputMap = new HashMap();
for(String str : strs) {
int[] input = new int[26];
for(int i = 0; i < str.length(); i++) {
input[str.charAt(i) - 'a']++;
}
String inputStr = Arrays.toString(input);
if(outputMap.containsKey(inputStr)) {
outputMap.get(inputStr).add(str);
} else {
List<String> outputLst = new ArrayList();
outputLst.add(str);
outputMap.put(inputStr, outputLst);
}
}
output.addAll(outputMap.values());
return output;
}
3条答案
按热度按时间azpvetkf1#
中 的 每 一 个
输出 键 为 [ 1 ， 0 ， 0 ， 0 ， 1 ， 0 ， 0 ， 0 ， 0 ， 0 ， 0 ， 0 ， 0 ， 0 ， 0 ， 0 ， 0 ， 0 ， 0 ， 1 ， 0 ， 0 ， 0 ， 0 ， 0 ， 0 ， 0 ， 0 ] 。 这 是 数组 的 字符 串 表示 形式 ， 其中 每个 索引 表示 从 * * a ， b ， c * * 到 * * z * * 的 每个 字母 的 出现 次数 。
对于 任何 一 个 变位 词 ， 所有 可能 的 英文 字母 出现 的 次数 都 是 相同 的 ， 所以 数组 的 字符 串 表示 也 是 相同 的 ， 这 就是 为什么 outputMap . containsKey （ inputStr ） 会 建议 变位 词 已经 存在 于 相同 的 字母 组合 中 ， 并 将 新 的 字母 添加 到 现有 的 列表 中 。
时间 复杂 度 是 O （ m * n ） ， 其中 m 是 输入 列表 中 的 字符 串 个数 ， n 是 每个 字符 串 的 平均 字母 数 。 有 一 个 循环 运行 1 到 m 次 。 然后 我们 有 一 个 内部 循环 ， 每个 字符 串 运行 n 次 （ 字母 数 ） 。 所以 它 是 （ m * n ） 。
O （ 1 ） 时间 复杂 度 ： O （ 1 ） 时间 复杂 度 ： O （ 1 ） 时间 复杂 度 ： O （ 1 ） 时间 复杂 度 ： O （ 1 ） 时间 复杂 度
格式
所以 如果 我们 去掉 常数 部分 ， * * 时间 复杂 度 变成 O （ m * n ） * * 。
whhtz7ly2#
对于您的第一个问题“
What are we trying to do in the step where we convert sArr to string in this line - String test = Arrays.toString(sArr);“，我假设您指的是将input转换为inputStr的行。基本上，它是这样做的，
input数组代表一个数组，计算单词中的每个字母，用0 - 25，a - z表示.通过使用
Arrays.toString(input)将其转换为字符串，这样任何变位词都将由相同字符模式的字符串表示。例如，"abc"将等效于[1, 1, 1,...]，它将匹配"abc", "cba", "cab", "bca",或"bac"。（不确定我是否遗漏了一个）。对于你的第二个问题，“
What's the time complexity?“，我不是100%肯定，因为时间复杂度不是我的强项，但它似乎是正确的。我发现一个类似的leetcode解决方案是this，它与你的非常相似，是O（m*n）。km0tfn4u3#
Arrays.toString()返回指定数组内容的字符串表示形式。在您的示例中，它对输入进行编码以记录每个字符在其中的出现次数。以 eat 为例，它的编码为[1，0，0，0，1，0，0，0，0，0，0，0，0，0，0，0，0，0，0，1，0，0，0，0，0，0，0，0，0，0，0，0，0，0，0，0，0，0，0，0，0，0，0，0，0，0，0，0，0，0，0，0，0，0，0，0，0，0，0，0，0，0，0，0，0，0，0，0，0，0，0，0，0，0，OutputMap的键是一个编码，对应的值是具有相同编码的输入，换句话说，是变位词。我们进一步检查它是否作为键存在于Map中，以避免将输入添加到空列表并抛出异常。因此，OutputMap中的每个条目都是一个变位词组。我们需要遍历每一个长度为n的输入进行编码，这需要O（n）的时间，而每个循环包含m个输入，所以总的时间复杂度是O（m*n）。