给你一个仅由小写英文字母组成的字符串 s 。在一步操作中,你可以完成以下行为: 选则 s 的任一非空子字符串,可能是整个字符串,接着将字符串中的每一个字符替换为英文字母表中的前一个字符。例如,'b' 用 'a' 替换,'a' 用 'z' 替换。 返回执行上述操作 恰好一次 后可以获得的 字典序最小 的字符串。 子字符串 是字符串中的一个连续字符序列。 现有长度相同的两个字符串 x 和 字符串 y ,在满足 x[i] != y[i] 的第一个位置 i 上,如果 x[i] 在字母表中先于 y[i] 出现,则认为字符串 x 比字符串 y 字典序更小
时间: 2024-03-25 08:41:22 浏览: 122
将字符串中的非字母字符删除,将所有大写字母字符转换成小写字母字符,并显 示处理结果 字符串可以直接在定义时赋初值
可以通过模拟题目中的操作来解决这个问题。我们可以从左到右遍历字符串 s,记录当前找到的最小的字符 c,以及它所在的位置 i。如果当前字符比 c 小,那么我们就将 c 所在位置 i 到当前位置的子串进行一次操作,并将 c 替换成当前字符。因为我们希望操作后的字符串字典序最小,所以我们需要尽量将操作放在靠前的位置。
以下是一个示例代码实现:
```java
public class Solution {
public String findLexSmallestString(String s, int a, int b) {
int n = s.length();
char[] arr = s.toCharArray();
// 定义一个函数,用于将字符数组中的每个数字加上 a
// 注意,这里加上 a 可能会使得某些字符超出 'z' 的范围
// 但是这不影响结果,因为我们只需要比较字符串的字典序
// 超出 'z' 范围的字符会被当做比 'z' 大的字符处理
// 例如,'{' 比 'z' 大
Function<char[], char[]> addA = (char[] x) -> {
for (int i = 1; i < n; i += 2) {
x[i] = (char) ((x[i] - '0' + a) % 10 + '0');
}
return x;
};
// 定义一个函数,用于将字符数组向右循环移动 b 个位置
Function<char[], char[]> rotate = (char[] x) -> {
char[] res = new char[n];
for (int i = 0; i < n; i++) {
res[(i + b) % n] = x[i];
}
return res;
};
// 记录当前找到的最小字符 c,以及它所在的位置 i
char c = 'z';
int idx = -1;
// 枚举所有的 i,将区间 [i, n) 进行一次操作
for (int i = 0; i < n; i++) {
if (arr[i] < c) {
c = arr[i];
idx = i;
}
}
// 对区间 [idx, n) 进行一次操作
char[] tmp = Arrays.copyOfRange(arr, idx, n);
tmp = addA.apply(tmp);
tmp = rotate.apply(tmp);
for (int i = idx; i < n; i++) {
arr[i] = tmp[i - idx];
}
return new String(arr);
}
}
```
该算法的时间复杂度为 O(n^2),其中 n 是字符串的长度。因为我们需要枚举所有的 i,并对区间 [i, n) 进行一次操作。空间复杂度为 O(n),因为我们需要存储字符数组和临时数组。
阅读全文