Чем отличается Regex.Replace(...) от string.Replace(...)?

Question

[LuVairo]

Нужно написать алгоритм, который заменит все вхождения строки initial в строку line на final.
Так нужно делать до тех пор, пока в строке line не останется фрагментов равных initial.

Пример входных данных:
line = "abbacabba"
initial = "ba"
final = "a"
Выходные данные: aaacaaa

Я написал две реализации: с использованием string.Replace(...) и с Regex.Replace(...)
Первая версия проходит все тесты, но не укладывается по времени.
А вот вторая выдаёт неправильный ответ на 6/10 тесте (К сожалению, тесты скрыты).
Как такое возможно? Разве Regex.Replace(...) и string.Replace(...) работают по-разному?

Первая реализация:

static string ReplacedStringWithRegex(string line, string initial, string final)
{
    while (line.Contains(initial))
        line = Regex.Replace(line, initial, final);

    return line;
}

Вторая реализация:

static string ReplacedStringWithoutRegex(string line, string initial, string final)
{
    while (line.Contains(initial))
        line = line.Replace(initial, final);

    return line;
}

Answer 1

[Василий Банников]

Чем отличается Regex.Replace(...) от string.Replace(...)

Regex.Replace использует регулярные выражения для поиска того, что надо заменить.
string.Replace же ищет только по точному совпадению.

Соответственно, если переменная initial будет содержать какие-то специальные символы (например *, + и ?), то их поведение будет различаться.

Comments

[LuVairo]

Можно ли как-то игнорировать эти символы?

[Василий Банников]

LuVairo, да, использовать string.Replace.
Он должен быть и быстрее, чем Regex.Replace

[LuVairo]

Василий Банников, к сожалению, для больших строк string.Replace(...) не является эффективным (в контексте этой задачи)

[Василий Банников]

LuVairo, значит нужно смотреть на условия задачи и думать, как можно ускорить.

Regex.Replace принципиально не может быть быстрее, чем string.Replace.

Например в твоём коде Replace вызывается в цикле, что будет приводить к постоянным копированиям и реаллокациям.

Я бы попробовал тут использовать StringBuilder, чтобы выделить память 1 раз