algorithm - 如何替换字符串中的问号以使相同的字母不会彼此相邻出现？

Question

我编写了下面的代码来替换字符串中的每个问号，这样相同的字母就不会出现在彼此旁边。例如:

输入

ab?ac?

输出

abcaca

请注意，? 应替换为任何小写字母:[a-z]

下面是我的解决方案。但我的问题是:有没有更优化的方法来解决这个问题？

public String solution(String riddle) {
    char alpha[] = "abcdefghijklmnopqrstuvwxyz".toCharArray();
    if (riddle == null || riddle.indexOf('?') == -1) {
        return riddle;
    }
    StringBuilder sb = new StringBuilder("");
    int cnt = 0;
    for (int i = 0; i < riddle.length(); i++) {
        char current = riddle.charAt(i);
        char prev = '\0';
        char next = '\0';
        if (current == '?') {
            current = alpha[cnt];
            if (i != 0) {
                prev = sb.toString().charAt(i - 1);
            }
            if (i != riddle.length() - 1) {
                next = riddle.charAt(i + 1);
            }
            while (current == prev || current == next) {
                current = alpha[++cnt];
                if (cnt % 25 == 0) {
                    cnt = 0;
                }
            }
            sb.append(current);
        } else {
            sb.append(current);
        }
    }
    return sb.toString();
}

Answer 1

由于此转换为字符串，您的算法的时间复杂度降低到 O(n²):

prev = sb.toString().charAt(i - 1); 

此.toString 调用需要的时间与sb 的当前长度成线性关系。这确实是不必要的，因为 .charAt 也可以在 StringBuilder 实例上使用。所以快速解决方法是:

prev = sb.charAt(i - 1); 

现在代码将以 O(n) 的时间复杂度运行，并且无法进一步改进。

但是，您仍然可以通过以下观察获得一些时间:

• 没有必要用 charAt 获取 prev，因为你可以在 prev = current每次迭代结束(并相应地更改其范围)。

• 没有必要为 ? 寻找 26 个备选字母。每个问号都可以变成 a、b 或 c。不需要其他字母——你只需要三个(任何三个不同的字母都可以)。所以不需要alpha，不需要cnt，也不需要对它应用余数运算符。一个简单的三元表达式就可以完成这项工作。

• 您可以避免代码重复并将 append 调用移出 if...else block 。

下面是代码的样子:

public String solution(String riddle) {
    if (riddle == null || riddle.indexOf('?') == -1) {
        return riddle;
    }
    StringBuilder sb = new StringBuilder("");
    char prev = '\0';
    for (int i = 0; i < riddle.length(); i++) {
        char current = riddle.charAt(i);
        if (current == '?') {
            char next = '\0';
            if (i != riddle.length() - 1) {
                next = riddle.charAt(i + 1);
            }
            current = prev != 'a' && next != 'a' ? 'a'
                    : prev != 'b' && next != 'b' ? 'b'
                    : 'c';
        }
        sb.append(current);
        prev = current;
    }
    return sb.toString();
}