Tugas · string sulit 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 Lunaselesai · 15 dari 15 pengujianrespons dalam 2.9 dtk · waktu eksekusi 409 md · $0.0001

  ✓	shortest_palindrome("aacecaaa")diharapkan "aaacecaaa"	2 md
  ✓	shortest_palindrome("abcd")diharapkan "dcbabcd"	<1 md
  ✓	shortest_palindrome("")diharapkan ""	21 md

  ✓ 2 md✓ 1 md✓ <1 md✓ 1 md✓ 3 md✓ 2 md✓ 2 md✓ 2 md✓ 2 md⏱ 179 md⏱ 88 md⏱ 104 md
  Kode

  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 Argonselesai · 15 dari 15 pengujianrespons dalam 17 dtk · waktu eksekusi 518 md · $0.0036

  ✓	shortest_palindrome("aacecaaa")diharapkan "aaacecaaa"	2 md
  ✓	shortest_palindrome("abcd")diharapkan "dcbabcd"	2 md
  ✓	shortest_palindrome("")diharapkan ""	4 md

  ✓ <1 md✓ <1 md✓ 3 md✓ <1 md✓ <1 md✓ 1 md✓ 2 md✓ <1 md✓ <1 md⏱ 267 md⏱ 77 md⏱ 155 md
  Kode

  /**
   * @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.7selesai · 15 dari 15 pengujianrespons dalam 47 dtk · waktu eksekusi 590 md · $0.02

  ✓	shortest_palindrome("aacecaaa")diharapkan "aaacecaaa"	3 md
  ✓	shortest_palindrome("abcd")diharapkan "dcbabcd"	3 md
  ✓	shortest_palindrome("")diharapkan ""	<1 md

  ✓ 2 md✓ 2 md✓ 2 md✓ 1 md✓ <1 md✓ <1 md✓ <1 md✓ <1 md✓ 1 md⏱ 265 md⏱ 168 md⏱ 139 md
  Kode

  /**
   * @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 Nexttidak selesai · 6 dari 15 pengujianrespons dalam 7.7 dtk · waktu eksekusi 403 md · $0.0005

  ✓	shortest_palindrome("aacecaaa")diharapkan "aaacecaaa"	3 md
  ✗	shortest_palindrome("abcd")diharapkan "dcbabcd"hasil "cbaabcd"	2 md
  ✓	shortest_palindrome("")diharapkan ""	1 md

  ✓ 3 md✓ 1 md✗ jawaban salah✓ 4 md✗ jawaban salah✗ jawaban salah✗ jawaban salah✓ 5 md✗ jawaban salah⏱ jawaban salah⏱ jawaban salah⏱ jawaban salah
  Kode

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

  Percobaan kedua

  selesai · 15 dari 15 pengujianrespons dalam 4.2 dtk · $0.0003

  Model melihat berapa banyak tes yang gagal, contoh yang gagal beserta nilai yang diharapkan dan yang dihasilkan, serta hanya alasan mengapa tes tersembunyi gagal, bukan inputnya. Tidak memengaruhi peringkat atau rating.

  ✓	shortest_palindrome("aacecaaa")diharapkan "aaacecaaa"	1 md
  ✓	shortest_palindrome("abcd")diharapkan "dcbabcd"	<1 md
  ✓	shortest_palindrome("")diharapkan ""	<1 md

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

  Kode

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

Biaya token: $0.03 · Cara babak dijalankan dan dinilai →