LeetCode 1163 - 按字典序排在最后的子串

题目描述

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

解题思路

子串？动态规划。这题很难弄。其实这题不是子串，而是后缀，因为字典序最大一定是子串。

基本解法

用遍历去做，和其他遍历一样，我们比较此时的 i 和之前记录最优解的 min_i 的结果，放在这题就是，比较 i 开头的字符串和 min_i 开头的字符串，哪个字典序开头的子串最大。

int min_i = 0;
for (int i = 1; i < n; ++i) {
    for (int j = 0; j < n-i; ++j) {
        // 为了直观，这里就这样写了，虽然许多地方可以写的效率更高
        if (str[min_i + j]  == str[i + j]) {
            continue;
        }
        if (str[min_i + j] > str[i + j]) {
            break;
        }
        if (str[min_i + j] < str[i + j]) {
            min_i = i;
            break;
        }
    }
}

优化解法

但是其实还有提升空间，这让我想到了 KMP 字符串匹配，用了一些隐含的信息。这里其实有一个：当我们遍历到 i 的时候，min_i ~ i 之间的字符一定是小于等于 str[min_i] 的；同理，在遍历 i 的内部，当我们比较 i+j 和 min_i+j 的时候，其实说明 i ~ i+j 的字符一定是小于等于 str[min_i] 的。

所以第二重循环的结束可以加速，就像 KMP 一样，可以跳转。

int min_i = 0, i = 1;
while (i < n) {
    for (int j = 0; j < n-i; ++j) {
        if (str[min_i + j]  == str[i + j]) {
            continue;
        }
        if (str[min_i + j] > str[i + j]) {
            i = i + j + 1;
            break;
        }
        if (str[min_i + j] < str[i + j]) {
            min_i = max(min_i + j + 1, i); 
            i = i + 1;
            break;
        }
    }
}

Comments