Opdracht · strings moeilijk 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 Lunaopgelost · 15 van 15 testsantwoord in 2.9 s · looptijd 409 ms · $0.0001

  ✓	shortest_palindrome("aacecaaa")verwacht "aaacecaaa"	2 ms
  ✓	shortest_palindrome("abcd")verwacht "dcbabcd"	<1 ms
  ✓	shortest_palindrome("")verwacht ""	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 Argonopgelost · 15 van 15 testsantwoord in 17 s · looptijd 518 ms · $0.0036

  ✓	shortest_palindrome("aacecaaa")verwacht "aaacecaaa"	2 ms
  ✓	shortest_palindrome("abcd")verwacht "dcbabcd"	2 ms
  ✓	shortest_palindrome("")verwacht ""	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.7opgelost · 15 van 15 testsantwoord in 47 s · looptijd 590 ms · $0.02

  ✓	shortest_palindrome("aacecaaa")verwacht "aaacecaaa"	3 ms
  ✓	shortest_palindrome("abcd")verwacht "dcbabcd"	3 ms
  ✓	shortest_palindrome("")verwacht ""	<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 Nextniet opgelost · 6 van 15 testsantwoord in 7.7 s · looptijd 403 ms · $0.0005

  ✓	shortest_palindrome("aacecaaa")verwacht "aaacecaaa"	3 ms
  ✗	shortest_palindrome("abcd")verwacht "dcbabcd"teruggegeven "cbaabcd"	2 ms
  ✓	shortest_palindrome("")verwacht ""	1 ms

  ✓ 3 ms✓ 1 ms✗ verkeerd antwoord✓ 4 ms✗ verkeerd antwoord✗ verkeerd antwoord✗ verkeerd antwoord✓ 5 ms✗ verkeerd antwoord⏱ verkeerd antwoord⏱ verkeerd antwoord⏱ verkeerd antwoord
  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;
  }

  Tweede poging

  opgelost · 15 van 15 testsantwoord in 4.2 s · $0.0003

  Het model zag hoeveel tests er faalden, de mislukte voorbeelden met de verwachte en geretourneerde waarden, en alleen waarom verborgen tests faalden, niet hun inputs. Telt niet mee voor de eindstand of rating.

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

Tokenkosten: $0.03 · Hoe rondes verlopen en worden beoordeeld →