给出了n个单词的数组。每个单词都由小写字母组成（“a”-“z”）。我们的目标是以这样的方式连接单词，以便获得一个单词，其中包含由一个特定字母组成的尽可能长的子字符串。找出这样一个子串的长度。
示例：
给定n=3和words=['aabb'，'aaaa'，'bbab']，函数应该返回6。最好的连接方式之一是单词[1]+单词[0]+单词[2]='aaaaaa bbbbab'。最长的子字符串由字母“a”组成，其长度为6。
给定n=3和words=['xxbxx'，'xbx'，'x']，函数应该返回4。最好的连接方式之一是单词[0]+单词[2]+单词[1]='xxbxxbx'。最长的子字符串由字母“x”组成，其长度为4。
我知道我不应该张贴的答案，但可能会帮助某人谁是寻找一个最佳的解决方案。
class DailyCodingProblem4 {
public static void main(String args[]) {
String[] arr = { "aabb", "aaaa", "bbab" };
int res = solution(arr);
System.out.println(res);
String[] arr2 = { "xxbxx", "xbx", "x" };
res = solution(arr2);
System.out.println(res);
}
private static int solution(String[] arr) {
Map<Integer, Integer> prefix = new HashMap<>();
Map<Integer, Integer> suffix = new HashMap<>();
Map<Integer, Integer> both = new HashMap<>();
for (int i = 0; i < arr.length; i++) {
String word = arr[i];
int j = 1;
while (j < word.length() && word.charAt(0) == word.charAt(j)) {
j++;
}
int key = word.charAt(0);
if (j == word.length()) {
if (both.containsKey(key)) {
Integer temp = both.get(key);
if (j > temp) {
both.put(key, j);
}
} else {
both.put(key, j);
}
} else {
if (suffix.containsKey(key)) {
Integer temp = suffix.get(key);
if (j > temp) {
suffix.put(key, j);
}
} else {
suffix.put(key, j);
}
j = word.length() - 1;
while (j > 0 && word.charAt(word.length() - 1) == word.charAt(j - 1)) {
j--;
}
key = word.charAt(word.length() - 1);
if (prefix.containsKey(key)) {
Integer temp = prefix.get(key);
if (word.length() - j > temp) {
prefix.put(key, word.length() - j);
}
} else {
prefix.put(key, word.length() - j);
}
}
}
int res = 0;
for (Integer key : prefix.keySet()) {
if (suffix.containsKey(key)) {
int temp = prefix.get(key) + suffix.get(key);
if (temp > res) {
res = temp;
}
}
}
for (Integer key : suffix.keySet()) {
if (prefix.containsKey(key)) {
int temp = prefix.get(key) + suffix.get(key);
if (temp > res) {
res = temp;
}
}
}
for (Integer key : both.keySet()) {
if (prefix.containsKey(key)) {
int temp = prefix.get(key) + both.get(key);
if (temp > res) {
res = temp;
}
}
if (suffix.containsKey(key)) {
int temp = both.get(key) + suffix.get(key);
if (temp > res) {
res = temp;
}
}
}
return res;
}
}
4条答案
按热度按时间bwntbbo31#
一种可能的解决方案是生成所有可能的组合，并找出最长长度的子串，包含相同的字符；
omqzjyyz2#
对于每封信，你需要知道：
完全由该字母组成的单词的总长度；
字母前缀最长和次长的单词；和
后缀最长和次长的单词
因为每个单词最多进入两个组，由它的开头和结尾字母决定，所以你可以在o（n）时间内搞清这一切。
db2dz4w83#
我用了带负键的多重Map。
后缀是负数，后缀是正数。
计数器用于跟踪位于中间的最长字符串，而无需在填充Map时串联。
多重Map将最大的数字自动排序为最负数和最正数
如果字符串仅由一个字符组成，则在将贴图填充为牌组上的小丑卡时，会将其串联起来。
Map的字段是[occurrence]
上面解释了出现的情况，char是所涉及的字母，bool是一个通配符小丑，不管怎样都会被添加。int以防止重新计算同一字符串（同一字符串上的后缀和前缀）。
2 while循环。1表示后缀偏移，1表示前缀偏移。返回最大值
在递归函数中，chk if bool，if so我们继续，直到找到下一个最大的前缀，它将最大化连接。
在递归函数中，如果初始情况不是bool，那么我们继续进行，直到找到小丑bool（见4）。看看为什么我们不需要走得更远）
添加对应的后缀（如果有的话）
这就是后缀偏差的重要性所在(7~9）是前缀偏差。这意味着我们可能会跳过最大的后缀。但是如果后缀足够大，那么后缀+任何小前缀和joker都有可能产生最长的字符串。因此，初始分支（见6.）比较最大偏差。
rt4zxlrg4#
对于一个特定的字母，它最长的子字符串可以用以下两种方式之一形成
它可以形成一个单词的后缀+所有完全由该字母组成的单词+另一个单词的前缀。例如
'abxaa' + 'aaa' + 'a' + 'abvdf'所以这里的子串长度'a'是7. 要获得最长的子串，您需要i） 获取该字符的最长后缀（不要包含只有该单词出现的单词，我们将在下一步使用它们）。例如在
['aabb','aaaa','bbab']和字母'a'这将是0因为没有单词'a'是一个严格的前缀。ii）获得只有该字母的所有单词的总长度。在这个例子中是这样的
4（英寸'aaaa').iii）执行步骤i），但现在执行严格的前缀。举个例子
2（英寸'aabb')iv）将上述三个步骤的值相加。你得到了吗
0 + 4 + 2 = 6例如字母'a'.子字符串可以完全位于单词内部。找出此类案例的最大长度。我们的例子是
1在('bbab').通过取这两个可能的解的最大值，你得到了该字母的最大长度子串。现在就为所有人表演这个
26字母，取最大值。我会把它留给你执行，但让我知道如果你面临任何问题。时间复杂性是O(Total length of all words).