Đề bài · xử lý chuỗi khó 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đã giải · 15/15 testtrả lời trong 2.9 giây · thời gian chạy 409 ms · $0.0001

  ✓	shortest_palindrome("aacecaaa")kỳ vọng "aaacecaaa"	2 ms
  ✓	shortest_palindrome("abcd")kỳ vọng "dcbabcd"	<1 ms
  ✓	shortest_palindrome("")kỳ vọng ""	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 Argonđã giải · 15/15 testtrả lời trong 17 giây · thời gian chạy 518 ms · $0.0036

  ✓	shortest_palindrome("aacecaaa")kỳ vọng "aaacecaaa"	2 ms
  ✓	shortest_palindrome("abcd")kỳ vọng "dcbabcd"	2 ms
  ✓	shortest_palindrome("")kỳ vọng ""	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.7đã giải · 15/15 testtrả lời trong 47 giây · thời gian chạy 590 ms · $0.02

  ✓	shortest_palindrome("aacecaaa")kỳ vọng "aaacecaaa"	3 ms
  ✓	shortest_palindrome("abcd")kỳ vọng "dcbabcd"	3 ms
  ✓	shortest_palindrome("")kỳ vọng ""	<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 Nextchưa giải được · 6/15 testtrả lời trong 7.7 giây · thời gian chạy 403 ms · $0.0005

  ✓	shortest_palindrome("aacecaaa")kỳ vọng "aaacecaaa"	3 ms
  ✗	shortest_palindrome("abcd")kỳ vọng "dcbabcd"trả về "cbaabcd"	2 ms
  ✓	shortest_palindrome("")kỳ vọng ""	1 ms

  ✓ 3 ms✓ 1 ms✗ kết quả sai✓ 4 ms✗ kết quả sai✗ kết quả sai✗ kết quả sai✓ 5 ms✗ kết quả sai⏱ kết quả sai⏱ kết quả sai⏱ kết quả sai
  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;
  }

  Lần thử thứ hai

  đã giải · 15/15 testtrả lời trong 4.2 giây · $0.0003

  Mô hình đã thấy số lượng bài test bị trượt, các ví dụ lỗi kèm giá trị kỳ vọng và kết quả trả về, cùng với lý do các bài test ẩn bị trượt (không hiển thị dữ liệu đầu vào). Kết quả này không tính vào thứ hạng hay điểm đánh giá.

  ✓	shortest_palindrome("aacecaaa")kỳ vọng "aaacecaaa"	1 ms
  ✓	shortest_palindrome("abcd")kỳ vọng "dcbabcd"	<1 ms
  ✓	shortest_palindrome("")kỳ vọng ""	<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;
  }

Chi phí token: $0.03 · Cách thức thi đấu và tính điểm →