Défi · chaînes difficile JavaScript ·

Shortest palindrome by prepending

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

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

• #1OpenAI GPT-6 Lunarésolu · 15 sur 15 testsréponse en 2.9 s · exécution 409 ms · $0.0001

  ✓	shortest_palindrome("aacecaaa")attendu "aaacecaaa"	2 ms
  ✓	shortest_palindrome("abcd")attendu "dcbabcd"	<1 ms
  ✓	shortest_palindrome("")attendu ""	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
  Code

  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 Argonrésolu · 15 sur 15 testsréponse en 17 s · exécution 518 ms · $0.0036

  ✓	shortest_palindrome("aacecaaa")attendu "aaacecaaa"	2 ms
  ✓	shortest_palindrome("abcd")attendu "dcbabcd"	2 ms
  ✓	shortest_palindrome("")attendu ""	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
  Code

  /**
   * @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.7résolu · 15 sur 15 testsréponse en 47 s · exécution 590 ms · $0.02

  ✓	shortest_palindrome("aacecaaa")attendu "aaacecaaa"	3 ms
  ✓	shortest_palindrome("abcd")attendu "dcbabcd"	3 ms
  ✓	shortest_palindrome("")attendu ""	<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
  Code

  /**
   * @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 Nextnon résolu · 6 sur 15 testsréponse en 7.7 s · exécution 403 ms · $0.0005

  ✓	shortest_palindrome("aacecaaa")attendu "aaacecaaa"	3 ms
  ✗	shortest_palindrome("abcd")attendu "dcbabcd"obtenu "cbaabcd"	2 ms
  ✓	shortest_palindrome("")attendu ""	1 ms

  ✓ 3 ms✓ 1 ms✗ mauvaise réponse✓ 4 ms✗ mauvaise réponse✗ mauvaise réponse✗ mauvaise réponse✓ 5 ms✗ mauvaise réponse⏱ mauvaise réponse⏱ mauvaise réponse⏱ mauvaise réponse
  Code

  /**
   * @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;
  }

  Second essai

  résolu · 15 sur 15 testsréponse en 4.2 s · $0.0003

  Le modèle a eu accès au nombre de tests échoués, aux exemples en échec avec les valeurs attendues et obtenues, ainsi qu'au motif d'échec des tests cachés (sans leurs entrées). Ne compte ni pour le classement ni pour l'évaluation.

  ✓	shortest_palindrome("aacecaaa")attendu "aaacecaaa"	1 ms
  ✓	shortest_palindrome("abcd")attendu "dcbabcd"	<1 ms
  ✓	shortest_palindrome("")attendu ""	<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

  Code

  /**
   * @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;
  }

Coût en jetons: $0.03 · Déroulement et calcul des scores →