Не могу разобраться с этим основным алгоритмом, включающим простой цикл for?

Question

Рассмотрим строку, первая буква которой всегда "M", а другими символами могут быть любые комбинации "I"s и "U"s (никакие другие буквы не допускаются, только Is и Us). Например: MIU, MUI, MIUIU, MUIIUIU, MUIIIUIIIUIII, MIUUIUIIIUUI - все строки этого типа.

Я хочу, чтобы функция, которая давала любую такую ​​строку в качестве входных данных, возвращала массив всеми возможными способами, которыми шаблон "III" может, если он вообще присутствует во входной строке, быть заменен на "U" во входных данных. Например, есть 2 способа, которыми "III" можно заменить на "U" в "MIIII", а именно MUI и MIU. Следовательно, функция, учитывая MIIII в качестве входных данных, должна возвращать [MUI, MIU].

Это моя (некорректная) функция. Идея, лежащая в основе этого, заключается в том, чтобы циклически проходить по входной строке (т.е. MIstring), ища "III". Каждый раз, когда "III" найден, MIstring добавляется в массив IIIoptions, но "U" заменяет "III".

function ruleThree() {
    var IIIoptions = [];
    for (var i = 0; i < MIstring.length; i++) {
        if (MIstring.slice(i, i+3) === "III") {          
           IIIoptions.push(MIstring.replace(MIstring.slice(i, i+3), "U"));
        }
    }
    return IIIoptions;
}

Учитывая ввод MIIII, я ожидал, что функция вернет [MUI, MIU]. Тем не менее, он возвращает [MUI, MUI]. Я пробовал с разными входами, и он отображает ту же проблему, то есть все элементы в массиве одинаковы. Например, учитывая строку MIIIIUIIIIU, она дает мне [MUIUIIIIU, MUIUIIIIU, MUIUIIIIU, MUIUIIIIU] вместо [MUIUIIIIU, MIUUIIIIU, MIIIIUUIU, MIIIIUIUU]. Таким образом, функция получает правильное число "III"s, содержащееся в MIstring, но не возвращает массив, который я ожидаю вернуть.

Что не так с моей функцией?

Answer 1

Основная проблема в том, что вы используете String.replace () , и этот метод всегда заменит первую совпадающую последовательность III на U так, как вы ее вызываете.Вы можете использовать String.slice () , чтобы сгенерировать новую строку с заменой при обнаружении совпадения, например:

const input = "MIIIII";

function ruleThree(str)
{
    var IIIoptions = [];

    for (var i = 0; i < str.length; i++)
    {
        if (str.slice(i, i + 3) === "III")
           IIIoptions.push(str.slice(0, i) + "U" + str.slice(i + 3));
    }
    
    return IIIoptions;
}

console.log(ruleThree(input));

.as-console {background-color:black !important; color:lime;}
.as-console-wrapper {max-height:100% !important; top:0;}

Однако обратите внимание, что предыдущий подход не удастся, если вам потребуется более одной замены за раз, например, если вы введете MIIIIII, он не будетгенерировать строку MUU.В этом случае вам придется использовать рекурсивный способ:

const input = "MIIIIIII";

function getCombs(str, res = new Set())
{
    for (var i = 0; i < str.length; i++)
    {
        if (str.slice(i, i + 3) === "III")
        {
           let r = str.slice(0, i) + "U" + str.slice(i + 3);
           res.add(r);
           getCombs(r, res);
        }
    }

    return [...res];
}

console.log(getCombs(input));

.as-console {background-color:black !important; color:lime;}
.as-console-wrapper {max-height:100% !important; top:0;}