مسئله · رشته‌ها سخت 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 · نحوه برگزاری راندها و امتیازدهی ←