X

LEETCODE 1163. Last Substring in Lexicographical Order 解题思路分析

题目大意:

按字典序排在最后的子串

给你一个字符串 s,找出它的所有子串并按字典序排列,返回排在最后的那个子串。

示例 1:

输入:"abab"
输出:"bab"
解释:我们可以找出 7 个子串 ["a", "ab", "aba", "abab", "b", "ba", "bab"]。按字典序排在最后的子串是 "bab"。

示例 2:

输入:"leetcode"
输出:"tcode"

示:

  1. 1 <= s.length <= 4 * 10^5
  2. s 仅含有小写英文字符。

如果想查看本题目是哪家公司的面试题,请参考以下免费链接: https://leetcode.jp/problemdetail.php?id=1163

解题思路分析:

题目要求找出字典顺序最大的子字符串,简单说下我的思路吧。首先应该想到,字典顺序最大的字符串的起始位置不能确定,但终点位置一定是字符串的末尾。也就是说这个最大的子字符串不会出现在字符串的中间位置。证明这一点很简单,因为对于任意一个位于元字符串中间的子串,其字典顺序一定小于该子串开头到元字符串末尾的子串,比如:字符串: “azzab”,中间的”zz”是相对较大的子串,但字典顺序中一定小于”zzab”。

接下来我们需要先找出最大的字符,然后将整个字符串按照该最大字符进行分割,如果出现连续的最大字符时则不能分割。举个例子,比如字符串”azzczbzc”,分割后应为:

a
zzc
zb
zc

分割后所有子串中字典顺序最大的一个(zzc)即是返回结果的开头,再加上该子串到原字符串末尾的部分即是返回结果(“zzc+zbzc”)。

实现代码:

public String lastSubstring(String s) {
    char[] arr=s.toCharArray(); // 将字符串转为数组
    char maxChar=arr[0]; // 找到最大字符
    int firstMaxCharIndex=0; // 第一个最大字符所在位置
    for(int i=1;i<s.length();i++){
        if(arr[i]>maxChar){
            maxChar=arr[i];
            firstMaxCharIndex=i;
        }
    }
    String max=""; // 以最大字符分割的子串
    StringBuilder sb=new StringBuilder(); // 当前子串
    // 从第一个最大字符所在位置开始循环
    for(int i=firstMaxCharIndex;i<s.length();i++){
        // 如果当前字符是最大字符,该字符前的部分是可以被分割的
        if(arr[i]==maxChar){
            // 该字符前的部分大于最大子串(字典顺序)
            if(sb.toString().compareTo(max)>0){
                // 更新最大子串
                max=sb.toString();
            }
            // 分割后清空当前子串
            sb=new StringBuilder();
            // 合并连续的最大字符
            for(int j=i;j<s.length();j++){
                if(arr[j]!=maxChar) break;
                sb.append(maxChar);
                i=j;
            }
        }else{
            // 当前字符不是最大字符
            // 将当前字符合并到当前子串
            sb.append(arr[i]);
        }
    }
    // 循环结束后将最后一部分未分割部分与最大子串比较
    if(sb.toString().compareTo(max)>0){
        max=sb.toString();
    }
    // 找到最大子串的开头位置
    int index = s.indexOf(max);
    // 截取并返回
    return s.substring(index);
}

本题解法执行时间为23ms。

Runtime: 23 ms, faster than 29.42% of Java online submissions for Last Substring in Lexicographical Order.

Memory Usage: 43.2 MB, less than 100.00% of Java online submissions for Last Substring in Lexicographical Order.

本网站文章均为原创内容,并可随意转载,但请标明本文链接
如有任何疑问可在文章底部留言。为了防止恶意评论,本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言,并会在第一时间对您的留言进行回复!欢迎交流!
本文链接: http://leetcode.jp/leetcode-1163-last-substring-in-lexicographical-order-解题思路分析/
Categories: leetcode
kwantong: