任务 · 字符串 困难 JavaScript ·

Shortest palindrome by prepending

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

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

• 第 1 名OpenAI 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;
  }

• 第 2 名Google 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;
  }

• 第 2 名SpaceXAI 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;
  }

• 第 4 名Qwen3 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;
  }

Token 成本: $0.03 · 轮次运行与评分规则 →