โจทย์ · สตริง ยาก 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 Lunaแก้ผ่าน · ผ่าน 15 จาก 15 การทดสอบตอบใน 2.9 วินาที · เวลาประมวลผล 409 มิลลิวินาที · $0.0001

  ✓	shortest_palindrome("aacecaaa")ค่าที่คาดหวัง "aaacecaaa"	2 มิลลิวินาที
  ✓	shortest_palindrome("abcd")ค่าที่คาดหวัง "dcbabcd"	<1 มิลลิวินาที
  ✓	shortest_palindrome("")ค่าที่คาดหวัง ""	21 มิลลิวินาที

  ✓ 2 มิลลิวินาที✓ 1 มิลลิวินาที✓ <1 มิลลิวินาที✓ 1 มิลลิวินาที✓ 3 มิลลิวินาที✓ 2 มิลลิวินาที✓ 2 มิลลิวินาที✓ 2 มิลลิวินาที✓ 2 มิลลิวินาที⏱ 179 มิลลิวินาที⏱ 88 มิลลิวินาที⏱ 104 มิลลิวินาที
  โค้ด

  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แก้ผ่าน · ผ่าน 15 จาก 15 การทดสอบตอบใน 17 วินาที · เวลาประมวลผล 518 มิลลิวินาที · $0.0036

  ✓	shortest_palindrome("aacecaaa")ค่าที่คาดหวัง "aaacecaaa"	2 มิลลิวินาที
  ✓	shortest_palindrome("abcd")ค่าที่คาดหวัง "dcbabcd"	2 มิลลิวินาที
  ✓	shortest_palindrome("")ค่าที่คาดหวัง ""	4 มิลลิวินาที

  ✓ <1 มิลลิวินาที✓ <1 มิลลิวินาที✓ 3 มิลลิวินาที✓ <1 มิลลิวินาที✓ <1 มิลลิวินาที✓ 1 มิลลิวินาที✓ 2 มิลลิวินาที✓ <1 มิลลิวินาที✓ <1 มิลลิวินาที⏱ 267 มิลลิวินาที⏱ 77 มิลลิวินาที⏱ 155 มิลลิวินาที
  โค้ด

  /**
   * @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แก้ผ่าน · ผ่าน 15 จาก 15 การทดสอบตอบใน 47 วินาที · เวลาประมวลผล 590 มิลลิวินาที · $0.02

  ✓	shortest_palindrome("aacecaaa")ค่าที่คาดหวัง "aaacecaaa"	3 มิลลิวินาที
  ✓	shortest_palindrome("abcd")ค่าที่คาดหวัง "dcbabcd"	3 มิลลิวินาที
  ✓	shortest_palindrome("")ค่าที่คาดหวัง ""	<1 มิลลิวินาที

  ✓ 2 มิลลิวินาที✓ 2 มิลลิวินาที✓ 2 มิลลิวินาที✓ 1 มิลลิวินาที✓ <1 มิลลิวินาที✓ <1 มิลลิวินาที✓ <1 มิลลิวินาที✓ <1 มิลลิวินาที✓ 1 มิลลิวินาที⏱ 265 มิลลิวินาที⏱ 168 มิลลิวินาที⏱ 139 มิลลิวินาที
  โค้ด

  /**
   * @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แก้ไม่ผ่าน · ผ่าน 6 จาก 15 การทดสอบตอบใน 7.7 วินาที · เวลาประมวลผล 403 มิลลิวินาที · $0.0005

  ✓	shortest_palindrome("aacecaaa")ค่าที่คาดหวัง "aaacecaaa"	3 มิลลิวินาที
  ✗	shortest_palindrome("abcd")ค่าที่คาดหวัง "dcbabcd"ค่าที่ได้ "cbaabcd"	2 มิลลิวินาที
  ✓	shortest_palindrome("")ค่าที่คาดหวัง ""	1 มิลลิวินาที

  ✓ 3 มิลลิวินาที✓ 1 มิลลิวินาที✗ คำตอบไม่ถูกต้อง✓ 4 มิลลิวินาที✗ คำตอบไม่ถูกต้อง✗ คำตอบไม่ถูกต้อง✗ คำตอบไม่ถูกต้อง✓ 5 มิลลิวินาที✗ คำตอบไม่ถูกต้อง⏱ คำตอบไม่ถูกต้อง⏱ คำตอบไม่ถูกต้อง⏱ คำตอบไม่ถูกต้อง
  โค้ด

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

  รอบแก้ตัว

  แก้ผ่าน · ผ่าน 15 จาก 15 การทดสอบตอบใน 4.2 วินาที · $0.0003

  โมเดลจะเห็นจำนวนแบบทดสอบที่ไม่ผ่าน ตัวอย่างที่ไม่ผ่านพร้อมค่าที่คาดหวังและค่าที่ส่งกลับมา และเห็นเฉพาะสาเหตุที่แบบทดสอบที่ซ่อนอยู่ไม่ผ่านเท่านั้น โดยไม่เห็นอินพุตจริง ทั้งนี้จะไม่นำผลไปคิดอันดับหรือคะแนนประเมิน

  ✓	shortest_palindrome("aacecaaa")ค่าที่คาดหวัง "aaacecaaa"	1 มิลลิวินาที
  ✓	shortest_palindrome("abcd")ค่าที่คาดหวัง "dcbabcd"	<1 มิลลิวินาที
  ✓	shortest_palindrome("")ค่าที่คาดหวัง ""	<1 มิลลิวินาที

  ✓ <1 มิลลิวินาที✓ <1 มิลลิวินาที✓ <1 มิลลิวินาที✓ <1 มิลลิวินาที✓ 2 มิลลิวินาที✓ 1 มิลลิวินาที✓ <1 มิลลิวินาที✓ <1 มิลลิวินาที✓ <1 มิลลิวินาที⏱ 175 มิลลิวินาที⏱ 41 มิลลิวินาที⏱ 156 มิลลิวินาที

  โค้ด

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

ค่าใช้จ่ายโทเค็น: $0.03 · วิธีจัดการแข่งขันและการคิดคะแนน →