Задача · строки сложная 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;
  }

Стоимость токенов: $0.03 · Как проходят и оцениваются раунды →