Görev · dizgiler zor JavaScript ·

Shortest palindrome by prepending

Add as few characters as possible to the front of s to make it a palindrome, and return the result. s has lowercase letters only and can be up to 200,000 characters long.

İmza

/**
 * @param {string} s
 * @returns {string}
 */
function shortest_palindrome(s)

Örnekler

shortest_palindrome("aacecaaa")  // -> "aaacecaaa"
shortest_palindrome("abcd")  // -> "dcbabcd"
shortest_palindrome("")  // -> ""

Ayrıca süre sınırına tabi 9 gizli test ve 3 büyük girdi testi; girdileri gösterilmez. Görevler modellere İngilizce verilir.

#1OpenAI GPT-6 Lunaçözüldü · 15 / 15 testyanıt süresi: 2.9 sn · çalışma süresi 409 ms · $0.0001

✓	shortest_palindrome("aacecaaa")beklenen "aaacecaaa"	2 ms
✓	shortest_palindrome("abcd")beklenen "dcbabcd"	<1 ms
✓	shortest_palindrome("")beklenen ""	21 ms

✓ 2 ms✓ 1 ms✓ <1 ms✓ 1 ms✓ 3 ms✓ 2 ms✓ 2 ms✓ 2 ms✓ 2 ms⏱ 179 ms⏱ 88 ms⏱ 104 ms

Kod

function shortest_palindrome(s) {
  const n = s.length;
  if (n < 2) return s;

  // Compute the longest palindromic prefix via the KMP prefix function
  // on s followed by a separator and the reverse of s.
  const rev = s.split('').reverse().join('');
  const text = s + '#' + rev;
  const pi = new Uint32Array(text.length);

  for (let i = 1; i < text.length; i++) {
    let j = pi[i - 1];
    while (j > 0 && text[i] !== text[j]) j = pi[j - 1];
    if (text[i] === text[j]) j++;
    pi[i] = j;
  }

  const palPrefixLength = pi[text.length - 1];
  return rev.slice(0, n - palPrefixLength) + s;
}

#2Google Gemini 4 Argonçözüldü · 15 / 15 testyanıt süresi: 17 sn · çalışma süresi 518 ms · $0.0036

✓	shortest_palindrome("aacecaaa")beklenen "aaacecaaa"	2 ms
✓	shortest_palindrome("abcd")beklenen "dcbabcd"	2 ms
✓	shortest_palindrome("")beklenen ""	4 ms

✓ <1 ms✓ <1 ms✓ 3 ms✓ <1 ms✓ <1 ms✓ 1 ms✓ 2 ms✓ <1 ms✓ <1 ms⏱ 267 ms⏱ 77 ms⏱ 155 ms

Kod

/**
 * @param {string} s
 * @returns {string}
 */
function shortest_palindrome(s) {
    const n = s.length;
    if (n <= 1) return s;

    // Reverse s
    let rev = "";
    for (let i = n - 1; i >= 0; i--) {
        rev += s[i];
    }

    if (s === rev) return s;

    const combined = s + "#" + rev;
    const m = combined.length;
    const pi = new Int32Array(m);

    let j = 0;
    for (let i = 1; i < m; i++) {
        while (j > 0 && combined.charCodeAt(i) !== combined.charCodeAt(j)) {
            j = pi[j - 1];
        }
        if (combined.charCodeAt(i) === combined.charCodeAt(j)) {
            j++;
        }
        pi[i] = j;
    }

    const longestPalindromicPrefixLen = pi[m - 1];
    return rev.slice(0, n - longestPalindromicPrefixLen) + s;
}

#2SpaceXAI Grok 4.7çözüldü · 15 / 15 testyanıt süresi: 47 sn · çalışma süresi 590 ms · $0.02

✓	shortest_palindrome("aacecaaa")beklenen "aaacecaaa"	3 ms
✓	shortest_palindrome("abcd")beklenen "dcbabcd"	3 ms
✓	shortest_palindrome("")beklenen ""	<1 ms

✓ 2 ms✓ 2 ms✓ 2 ms✓ 1 ms✓ <1 ms✓ <1 ms✓ <1 ms✓ <1 ms✓ 1 ms⏱ 265 ms⏱ 168 ms⏱ 139 ms

Kod

/**
 * @param {string} s
 * @returns {string}
 */
function shortest_palindrome(s) {
  const n = s.length;
  if (n <= 1) return s;
  const revArr = new Array(n);
  for (let i = 0; i < n; i++) {
    revArr[i] = s[n - 1 - i];
  }
  const temp = s + '#' + revArr.join('');
  const m = temp.length;
  const lps = new Array(m).fill(0);
  let len = 0;
  for (let i = 1; i < m; i++) {
    while (len > 0 && temp[i] !== temp[len]) {
      len = lps[len - 1];
    }
    if (temp[i] === temp[len]) {
      len++;
    }
    lps[i] = len;
  }
  const palLen = lps[m - 1];
  const suffixLen = n - palLen;
  if (suffixLen === 0) return s;
  const prependArr = new Array(suffixLen);
  for (let i = 0; i < suffixLen; i++) {
    prependArr[i] = s[n - 1 - i];
  }
  return prependArr.join('') + s;
}

#4Qwen3 Coder Nextçözülemedi · 6 / 15 testyanıt süresi: 7.7 sn · çalışma süresi 403 ms · $0.0005

✓	shortest_palindrome("aacecaaa")beklenen "aaacecaaa"	3 ms
✗	shortest_palindrome("abcd")beklenen "dcbabcd"dönen "cbaabcd"	2 ms
✓	shortest_palindrome("")beklenen ""	1 ms

✓ 3 ms✓ 1 ms✗ yanlış yanıt✓ 4 ms✗ yanlış yanıt✗ yanlış yanıt✗ yanlış yanıt✓ 5 ms✗ yanlış yanıt⏱ yanlış yanıt⏱ yanlış yanıt⏱ yanlış yanıt

Kod

/**
 * @param {string} s
 * @returns {string}
 */
function shortest_palindrome(s) {
    if (s.length === 0) return "";
    
    // Create the combined string: s + '#' + reverse(s)
    let rev = s.split('').reverse().join('');
    let combined = s + '#' + rev;
    
    // Compute the KMP failure function (longest proper prefix which is also suffix)
    let lps = new Array(combined.length).fill(0);
    
    for (let i = 1; i < combined.length; i++) {
        let j = lps[i - 1];
        
        while (j > 0 && combined[i] !== combined[j]) {
            j = lps[j - 1];
        }
        
        if (combined[i] === combined[j]) {
            j++;
        }
        
        lps[i] = j;
    }
    
    // The last value in lps tells us the longest prefix of s that matches a suffix of rev
    // This is the longest palindromic prefix of s
    let longestPrefixLen = lps[combined.length - 1];
    
    // The characters we need to prepend are the remaining part of rev
    let toPrepend = rev.substring(longestPrefixLen);
    
    return toPrepend + s;
}

İkinci deneme

çözüldü · 15 / 15 testyanıt süresi: 4.2 sn · $0.0003

Model kaç testin başarısız olduğunu, beklenen ve dönen değerlerle birlikte başarısız örnekleri ve gizli testlerin girdilerini değil yalnızca neden başarısız olduğunu gördü. Sıralamaya veya puana etki etmez.

✓	shortest_palindrome("aacecaaa")beklenen "aaacecaaa"	1 ms
✓	shortest_palindrome("abcd")beklenen "dcbabcd"	<1 ms
✓	shortest_palindrome("")beklenen ""	<1 ms

✓ <1 ms✓ <1 ms✓ <1 ms✓ <1 ms✓ 2 ms✓ 1 ms✓ <1 ms✓ <1 ms✓ <1 ms⏱ 175 ms⏱ 41 ms⏱ 156 ms

Kod

/**
 * @param {string} s
 * @returns {string}
 */
function shortest_palindrome(s) {
    if (s.length === 0) return "";
    
    // Build the LPS array for s + '#' + reverse(s)
    let rev = s.split('').reverse().join('');
    let combined = s + '#' + rev;
    
    // Compute KMP failure function (LPS array)
    let lps = new Array(combined.length).fill(0);
    
    for (let i = 1; i < combined.length; i++) {
        let j = lps[i - 1];
        
        while (j > 0 && combined[i] !== combined[j]) {
            j = lps[j - 1];
        }
        
        if (combined[i] === combined[j]) {
            j++;
        }
        
        lps[i] = j;
    }
    
    // The last value in lps gives us the length of the longest prefix of s
    // that matches a suffix of rev (which is the longest palindromic prefix of s)
    let longestPrefixLen = lps[combined.length - 1];
    
    // The characters we need to prepend are the remaining part of the reversed string
    // that doesn't overlap with the palindromic prefix
    let toPrepend = rev.substring(0, s.length - longestPrefixLen);
    
    return toPrepend + s;
}

Belirteç maliyeti: $0.03 · Turlar nasıl yürütülür ve puanlanır →