Leetcode - Defanging地址

Question

我正在使用C++在Leetcode上做IP defanging challenge。以下是我对解决方案的尝试：

class Solution {
public:
    string defangIPaddr(string address) {
        for(int i = 0; i < address.size(); i++){
            if(address[i] == '.'){
                address.replace(i, 1, "[.]");
            }
        }
        return address;
    }
};

在这里，代码不能用"[.]"替换句点，而是返回"Time Limit Exceeded“。

我尝试用"[]"替换它，它工作得很好，对于其他所有可能的字符串组合也是如此。我试着逃走，但还是不行。

"[.]"是不是一些无法读取的特殊字符串？我确实知道有一个解决方案，你可以迭代地连接字符串，但这不应该也起作用吗？

Answer 1

当循环遇到第一个.时，它会用[.]替换.，从而增加字符串的size。但是循环不会调整i来考虑新插入的[，所以下一次迭代将在新[之后看到相同的.，并一次又一次地执行相同的替换，一次又一次，无休止地执行。这就是你的解决方案超时的原因。

您需要确保前进的i超过了替换文本，例如：

class Solution {
public:
    string defangIPaddr(string address) {
        for(string::size_type i = 0; i < address.size(); ++i){
            if (address[i] == '.'){
                address.replace(i, 1, "[.]");
                i += 2; // <-- skip to ']', the subsequent ++i will then skip past it
            }
        }
        return address;
    }
};

Live Demo

或者，使用while循环而不是for循环，这样您就可以更容易地确定每次递增i的量：

class Solution {
public:
    string defangIPaddr(string address) {
        string::size_type i = 0;
        while (i < address.size()){
            if (address[i] == '.'){
                address.replace(i, 1, "[.]");
                i += 3;
            }
            else {
                ++i;
            }
        }
        return address;
    }
};

Live Demo

就我个人而言，我会在循环中使用std::string::find()，例如：

class Solution {
public:
    string defangIPaddr(string address) {
        string::size_type i = 0;
        while ((i = address.find('.', i)) != string::npos){
            address.replace(i, 1, "[.]");
            i += 3;
        }
        return address;
    }
};

Live Demo

Answer 2

让我们看一看示例输入bo.y。当i为2时，replace将字符串转换为bo[.]y。然后，当i为3时，它再次看到那个讨厌的.，replace将其转换为bo[[.]]y。这种情况会一直发生，直到超时。

解决方法？调用replace后递增i：

class Solution {
public:
    string defangIPaddr(string address) {
        for(int i = 0; i < address.size(); i++){
            if(address[i] == '.'){
                address.replace(i, 1, "[.]");
                i++;
            }
        }
        return address;
    }
};

Answer 3

正如在Remy's answer中所解释的，您的问题在于，当您增加字符串的长度时，循环计数器永远不会超过‘'.'’新字符。

尽管这个答案本身是完美无缺的，但我发现，在任何字符串替换和/或替换操作中，避免尝试做“内联”工作通常要简单得多；相反，在必要时替换复制的部分通常更容易：

class Solution {
public:
    string defangIPaddr(string address)
    {
        string answer{ "" }; // Local string to build the answer - start off empty.
        answer.reserve(address.size() * 2); // Reserve sufficient space to avoid multiple reallocation.
        for (size_t i = 0; i < address.size(); i++) {
            if (address[i] == '.') {
                answer += "[.]"; // For a dot, replace with the "[.]" string ...
            }
            else {
                answer += address[i]; // ... otherwsie, just copy the character.
            }
        }
        answer.shrink_to_fit(); // Free any unneeded memory.
        return answer; // We return BY VALUE, so a copy is made of the LOCAL "answer".
    }
};