串联字符串的最大长度 Posted on 2021-06-19 00:00:00 2021-06-26 00:00:00 by Author 摘要 给你一个字符串集合，你能按照题目要求完成本题吗？？(本题有点难度哦！！！！！) # 串联字符串的最大长度 1. 题目描述 - 给定一个字符串数组 `arr`，字符串 `s` 是将 `arr` 某一子序列字符串连接所得的字符串，如果 `s` 中的每一个字符都只出现过一次，那么它就是一个可行解。请返回所有可行解 `s` 中最长长度。 2. 示例描述 - 示例一 - 输入：arr = ["un","iq","ue"] - 输出：4 - 解释：所有可能的串联组合是 "","un","iq","ue","uniq" 和 "ique"，最大长度为 4。 - 示例二 - 输入：arr = ["cha","r","act","ers"] - 输出：6 - 解释：可能的解答有 "chaers" 和 "acters"。最长长度为6 3. 解题思路 - 首先拿到这个题目的时候，我还很懵逼，有点看不懂题目，然后多浏览了题目与示例才慢慢明白，这道题目大概意思就是，给你一个字符串集合，集合中的字符串，相互组合，但是组合后的字符串中每个字符不能出现多长，最多出现一次（字符串是由字符组成，意思是字符串中不能出现相同的字符）。 - 那么拿到这个题目时，首先我们解决的问题是，怎么判断两个字符串能不能合并。这里有一个思想就是`桶的思想`,因为字符串是由字符组成，而字符最多有26个，那么我们就定义一个大小为26的数组，判断每个字符串中是否出现重复的字符。如果没有，那么我们在桶中记录该字符串中有哪些字符，然后在判断另一个字符串是否包含相同的字符，如果第二个字符串没有出现相同的字符，那么在判断第二个字符串中的字符于第一个字符串的字符有没有重叠。如果有一个或者多个重叠，那么这两个字符串就不能合并，否则就能合并。这里只是通俗的讲一下实现思想，看了代码之和，你可能就会明白的。 - 第二步就是，让给定的字符串集合，相互组合。这里需要用到递归和回溯的思想。因为字符串集合中每个字符串都要于其他字符串相互组合(前提是能够相互组合并且合并的情况下)。 - 其中要用到递归是因为每个字符串要去其他字符串合并，用到回溯的思想是因为如下原因：假如给定一个字符串集合为[`"abc"`,`"def"`,`"ftyuio"`],假如第一个字符串于第二个字符串组合长度为：6，那么他们组合后，就不能于第三个字符串组合了，因为如果组合后就会出现相同的字符`f`,但是第一个字符串和最后一个字符串组合后他们的长度为：9，所以这里需要用到回溯的思想，那从那里体现出来尼，因为第一个字符串和第二个字符串，第三个字符串都能够组合，假如第一个字符串与第二个字符串组合后，就不能与第三个字符串组合了，但是第一个字符串和第二个字符串已经组合了，并且组合后的字符串已经变成`abcdef`，但是我们还要第一个字符串与第三个字符串组合，那我们就要回溯到，第一个字符串与第二个字符串还没合并的时候，之后第一个字符串就能和第三个字符串合并了，而且合并后的字符串长度大于与第二个字符合并的长度。那么最终结果就选最长的。 - 上面这个示例可能觉得意犹未尽，那我们在分析一下别的示例吧。假如给定一个字符串集合为：[`kxq`,`you`,`need`,`getup`,`abcefilhnzdyr`]，给了5个字符串，首先我们直奔主题，第一个字符串与其他字符串组合的集合有`[0,1]`,`[0,1,2]`,`[0,1,3]`,`[0,2]`,`[0,3,]`,`[0,4]`(集合中的数字代表集合下标)，首先假如第一个字符串和第二个字符第三个字符串组合后，就不能和最后两个字符串组合了，此时最大的长度为：10，但是第一个字符串可以和第二个字符串，第四个字符串相互组合啊，他们形成的长度为：11,假如第一个字符串和第二个，第三个字符串组合，就不能和第四个字符串组合了，而第一个字符串，第二个，第四个字符串组合的结果比前一个组合的结果长度大，此时我们需要从组合一中回溯到，字符串一与字符串二组合的位置，那么在这种状态下，就能和第四个字符串组合了。这里就用到了回溯的思想。 - 同时，第一个字符串与最后一个字符串也能组合，他们的长度大于之前所有的组合长度，所以，在第一个字符串与第二个字符串（第三个或者第四个字符串组合后）,需要回溯到只有第一个字符串的这种状态，在这样的状态下，才能与最后一个字符串相互组合，从而达到组合后长度最长的结果。 - 以上是我个人的理解，说实话，回溯和递归放在一起出的题目有点难，这需要慢慢积累和理解。如果有错误的地方和更好的讲解思路，欢迎骚扰我。下方是代码实现。 4. 代码实现 ```java //最终的结果，初值赋值为0 int result = 0; public int maxLength(List<String> arr) { //调用自己写的回溯与递归的方法 trackBack(arr, 0, ""); return result; } public void trackBack(List<String> arr, int index, String tempResult) { //每个字符串要与其他字符串相互组合，所以需要循环一次 for (int i = index; i < arr.size(); i++) { //如果组合后的字符串能与正在遍历的字符串合并 //那么就合并，并且寻找与其他字符串合并 if (isMerge(tempResult, arr.get(i))) { //这里就是递归与回溯 trackBack(arr, i + 1, tempResult + arr.get(i)); //其实上面一句调用方法可以写成下面三句的形式，更容易理解 /** //如果能够合并，那么就把当前遍历的字符串合并最终的字符串中 tempResult = tempResult + arr.get(i); //然后继续向下遍历,寻找下一个可以合并的字符串 trackBack(arr, i + 1, tempResult); //这里就是回溯的思想，回溯到一个可以与其他字符串合并的状态 tempResult = tempResult.substring(0,tempResult.length()-arr.get(i).length()); **/ } } //一次遍历完成后，找出合并后的最大值 result = Math.max(result, tempResult.length()); } //这个方法判断两个字符串是否可以合并 public boolean isMerge(String s1, String s2) { //首先把给定的两个字符串转化后字符数组，便于后序的操作 char[] str1 = s1.toCharArray(); char[] str2 = s2.toCharArray(); //桶思想的原理。定义一个大小为26的桶 int[] bucket = new int[26]; //记录字符串一出现哪些字符 for (int i = 0; i < s1.length(); i++) { //如果字符串一中自己都要重复的字符，那么直接返回false,他与其他字符串都不能合并 if (bucket[str1[i] - 'a'] != 0) { return false; } //否则记录，字符串一中出现了哪些字符 bucket[str1[i] - 'a'] = 1; } //判断字符串二是否出现了与字符串一相同的字符 for (int i = 0; i < s2.length(); i++) { //这一步即判断了字符串二中是否出现与字符串一中相同的字符(因为桶中已经记录字符串一出现的字符，发现相同，就说明重叠了) //也判断了字符串二本身是否有重复的字符 if (bucket[str2[i] - 'a'] != 0) { return false; } //如果没有出现重叠且字符串二本身没有重复的字符， // 那么就把当前字符记录桶中，为了后序操作中字符串二判断是否之前出现过该字符 bucket[str2[i] - 'a'] = 1; } //如果以上情况都没有，说明这两个字符串可以合并，返回true return true; } ```
{{ item.content }}
{{ child.content }}