المهمة · سلاسل نصية صعب 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 · كيف تُدار الجولات وتُحتسب النقاط ←