typescript - Varför misslyckas denna kod för ett testfall i Leetcode-problemet även om jag kom fram till en bättre lösning än vad som förväntades?

Jag löser LeetCode-problem 2193. Minsta antal drag för att göra en palindrom:

Du får en sträng s som endast består av små engelska bokstäver.

I ett drag kan du välja vilka som helst två intilliggande tecken i s och byta plats på dem.

Returnera minsta antalet drag som behövs för att göra s till en palindrom.

Observera att indata kommer att genereras så att s alltid kan omvandlas till en palindrom.

Jag löste problemet med denna TypeScript-kod:

function minMovesToMakePalindrome(s: string) {
    if (s.length <= 1) return 0;
    if (s[0] === s[s.length - 1]) return minMovesToMakePalindrome(s.slice(1, s.length - 1))
    let leftSwapsCost = s.length;
    let rightSwapsCost = s.length;
    for (let i = 0; i < s.length; i++) {
        if (s[i] === s[0]) {
            // we should swap with the last element
            rightSwapsCost = Math.min(rightSwapsCost, s.length - 1 - i)
        } else if (s[i] === s[s.length - 1]) {
            // we should swap with the first element
            leftSwapsCost = Math.min(leftSwapsCost, i)
        }
    }

    if (leftSwapsCost <= rightSwapsCost) {
        const newString = [s[leftSwapsCost], ...s.slice(1, leftSwapsCost), s[0], ...s.slice(leftSwapsCost + 1)].join('');
        console.log('left: ' + newString + ' cost: ' + leftSwapsCost)
        return leftSwapsCost + minMovesToMakePalindrome(newString.slice(1, s.length - 1))
    } else {
        const newString = [...s.slice(0, s.length - 1 - rightSwapsCost), s[s.length - 1], ...s.slice(s.length - rightSwapsCost, s.length - 1), s[s.length - 1 - rightSwapsCost]].join('');
        console.log('right: ' + newString + ' cost: ' + rightSwapsCost)
        return rightSwapsCost + minMovesToMakePalindrome(newString.slice(1, s.length - 1))
    }
};

I grunden traverserar jag matrisen av tecken (strängen) och letar efter indexet för de objekt som är lika med det första objektet och sedan beräknar jag kostnaden för att byta var och en av dessa med det sista objektet och lagrar minimivärdet av det i rightSwapsCost.

Samma sak för de föremål som är lika med det sista föremålet: jag beräknar minsta kostnad för att byta dem med det första föremålet och lagrar det i leftSwapsCost.

Slutligen gör jag bytet som kostar minst och anropar rekursivt den funktionen på den nya strängen newString (som erhållits efter bytet) som inte innehåller det första och sista elementet i den ursprungliga strängen före bytet.

Det klarade de initiala testfallen där S="aabb" och S="letelt"

Men när jag skickade in det accepterade det inte svaret i fallet där S="eqvvhtcsaaqtqesvvqch". Vilket är konstigt eftersom det faktiskt gjorde strängen till ett palindrom på färre steg än vad LeetCode förväntade sig.

Jag fick följande resultat:

Svar #1

Problemet är att du har utfört icke-intilliggande byten och felbedömt deras kostnad. Utmaningen frågar efter (minsta antal) adjacent-byten. Även om det förstås är okej att utföra icke-intilliggande byten och räkna ut hur många intilliggande byten som skulle behövas för att uppnå samma resultat, är denna beräkning fel.

Till exempel, för exempelindata ("eqvvhtcsaaqtqesvvqch") väljer din algoritm index 0 ("e") och 4 ("h") för ett byte, och antar att kostnaden för detta byte är 4, men det är fel. Vad som skulle ha kostat 4 är en rotation som placerar det "h" framför de 4 andra tecknen, som från "eqvvH" till "Heqvv" (jag använder avsiktligt versal för bokstaven som roteras), men inte ett byte från "EqvvH" till "HqvvE". Ändå är det den mutation din kod utför. Men kostnaden för ett sådant byte är större än 4! För att gå från "EqvvH" till "HqvvE" skulle du behöva göra 7 intilliggande byten:

eqvvH
eqvHv
eqHvv
eHqvv
Heqvv
hqEvv
hqvEv
hqvvE

Så implementera mutationerna som rotationer, inte som icke-intilliggande byten:

if (leftSwapsCost <= rightSwapsCost) {
    // Fixed:
    const newString = [s[leftSwapsCost], ...s.slice(0, leftSwapsCost), ...s.slice(leftSwapsCost + 1)].join('');
    console.log('left: ' + newString + ' cost: ' + leftSwapsCost)
    return leftSwapsCost + minMovesToMakePalindrome(newString.slice(1, s.length - 1))
} else {
    // Fixed:
    const newString = [...s.slice(0, s.length - 1 - rightSwapsCost), ...s.slice(s.length - rightSwapsCost), s[s.length - 1 - rightSwapsCost]].join('');
    console.log('right: ' + newString + ' cost: ' + rightSwapsCost)
    return rightSwapsCost + minMovesToMakePalindrome(newString.slice(1, s.length - 1))
}