如何替换字符串中的问号，以便相同的字母不会相邻出现？

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();
}

- Sadakul

---

它已经是O(n)了，我认为不可能比这更好了。 - Lrrr

Answer 1

您的算法时间复杂度因为将其转换为字符串而降级为O(n²)。

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

这个.toString调用需要与sb当前长度成线性关系的时间。而这是完全不必要的，因为StringBuilder实例上也可以使用.charAt。所以快速修复的方法是：

prev = sb.charAt(i - 1); 

现在，代码的时间复杂度为O(n)，这已经无法再进一步改进。

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

• 没有必要使用charAt来挑选出prev，因为你可以在每次迭代结束时进行prev = current赋值操作（并相应地更改其范围）。

• 不需要查看26个备选字母以找到?。每个问号可以变成a、b或c中的任何一个。不需要其他字母--只需要三个（任意三个不同的字母都可以）。因此，不需要alpha，也不需要cnt，也不需要对它应用余数运算符。一个简单的三元表达式就可以完成工作。

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

因此，代码可以如下所示：

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();
}

- trincot

Answer 2

Java 8的解决方案适用于所有输入场景。

public String solution(String input) {

    StringBuilder riddle = new StringBuilder(input); // convert string to string builder

    // handling when string is empty
    if (riddle.length() == 0) {
        return "";
    }

    // handling when there is only one character in the string
    if (riddle.length() == 1) {
        if (riddle.charAt(0) == '?') {
            return "a";
        } else {
            return riddle.toString();
        }
    }

    int count = 97;

    // running loop for input string whose length is more than 1
    for (int i = 0; i < riddle.length(); i++) {

        // handle the character at 0 index
        if (i == 0 && riddle.charAt(i) == '?') {
            riddle.setCharAt(i, (char) count);
            if (riddle.charAt(i) == riddle.charAt(i + 1)) {
                riddle.setCharAt(i, (char) (count + 1));
            }
        }

        count = 97;

        // handle the character between 0 and last index
        if (i != 0 && riddle.charAt(i) == '?' && i != riddle.length() - 1) {
            
            riddle.setCharAt(i, (char) count);
            
            while (count >= 97 && count <= 122) {
                if (riddle.charAt(i) == riddle.charAt(i + 1) || riddle.charAt(i) == riddle.charAt(i - 1)) {
                    riddle.setCharAt(i, (char) count);
                    count++;
                } else {
                    break;
                }
            }

        }

        count = 97;

        // handle the last character in the string
        if (i > 0 && i == riddle.length() - 1 && riddle.charAt(i) == '?') {

            riddle.setCharAt(i, (char) count);

            while (count >= 97 && count <= 122) {
                if (count == riddle.charAt(i - 1)) {
                    count++;
                    riddle.setCharAt(i, (char) count);

                } else {
                    break;
                }
            }

        }

    }

    return riddle.toString();

}

- mysteriousR