构造字典序最大的合并字符串【LC1754】
You are given two strings word1 and word2. You want to construct a string merge in the following way: while either word1 or word2 are non-empty, choose one of the following options:
- If word1 is non-empty, append the first character in word1 to mergeand delete it from word1
。For example, if word1 = "abc" and merge = "dv", then after choosing this operation, word1 = "bc" and merge = "dva".
- If word2is non-empty, append the first character in word2 to merge and delete it from word2
。For example, if word2 = "abc" and merge = "", then after choosing this operation, word2 = "bc" and merge = "a".
虽然烤红薯很好吃 但是被烤箱烫伤了瞬间就不香了
现在的医院全是咳嗽的哎 真可怕哎
- 思路：双指针遍历两个字符串，贪心比较字符的字典顺序，并添加至结果集
局部最优：优先选择后缀字符串的字典顺序较大的字符至结果集
全局最优：合并后的字符串的字典顺序最大
。如果两个指针对应的字符不相等，直接将字典顺序较大的字符加入结果集的末尾，并且移动改字符串对应的指针
。如果两个指针对应的字符相等，那么需要比较后缀字符串的字典顺序
- 添加较大者对应的字符至结果集
- 如果字典顺序相同，那么添加任意字符均不会影响结果
- 实现
。先使用双指针对字符进行比较直至移动到一个字符串的末尾
。此时直接将另一个非空字符串剩余的字符添加至结果集即可
class Solution { public String largestMerge(String word1, String word2) { StringBuilder sb = new StringBuilder(); int n = word1.length(), m = word2.length(); int i = 0, j = 0; while (i < n && j < m){ char ch1 = word1.charAt(i), ch2 = word2.charAt(j); if (ch1 > ch2){ sb.append(ch1); i++; }else if (ch1 < ch2){ sb.append(ch2); j++; }else{ // 字符相等 需要判断后续字符的字典顺序 if (i < n && word1.substring(i).compareTo(word2.substring(j)) > 0){ sb.append(ch1); i++; }else{ sb.append(ch2); j++; } } } if (i < n){ sb.append(word1.substring(i)); } if (j < m){ sb.append(word2.substring(j)); } return new String(sb); } }
。复杂度
- 时间复杂度：O(min(m,n)∗min(m,n))，m和n分别为字符串的长度，先压入字符进行比较，需要比较min(m,n)次，若两个字符串相等那么需要进行后缀比较的时间复杂度为O(min(m,n))次
- 空间复杂度：O(m+n)，生成的后缀字符串所需要的空间为O(m+n)
- 实现：每一次比较均比较后缀字符串
代码好看，时间复杂度稍微高一点
class Solution { public String largestMerge(String word1, String word2) { StringBuilder merge = new StringBuilder(); int i = 0, j = 0; while (i < word1.length() || j < word2.length()) { if (i < word1.length() && word1.substring(i).compareTo(word2.substring(j)) > 0) { merge.append(word1.charAt(i)); i++; } else { merge.append(word2.charAt(j)); j++; } } return merge.toString(); } } 作者：力扣官方题解 链接：https://leetcode.cn/problems/largest-merge-of-two-strings/solutions/2030226/gou-zao-zi-dian-xu-zui-da-de-he-bing-zi-g6az1/ 来源：力扣（LeetCode） 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
。复杂度
- 时间复杂度：O((m+n)∗max(m,n))，m和n分别为字符串的长度，先压入字符进行比较，需要比较(m+n)次，每次需要进行后缀比较的时间复杂度为O(max(m,n))次
- 空间复杂度：O(m+n)，生成的后缀字符串所需要的空间为O(m+n)
