[leetcode 5] Не могу найти, что не так в моем решении самой длинной проблемы с подстрокой палиндрома - PullRequest
Новая
       89

[leetcode 5] Не могу найти, что не так в моем решении самой длинной проблемы с подстрокой палиндрома

2 голосов
/ 05 августа 2020

ввод: 

babad
abbd

вывод: 

ad
bb

ожидается: 

bab
bb

Код: 

#include<iostream>
using namespace std;

class Solution {
public:
    string longestPalindrome(string s) {
        int maxlength=1;
        bool ispalindromic[1000][1000]={false};
        for(int i=0;i<s.length();i++)
            ispalindromic[i][i]=1;
                
        for(int l=2;l<s.length();l++){
            for(int i=0;i<s.length()-1; i++){
                int j=i+l-1;
                if(l==2&&s[i]==s[j]){
                    ispalindromic[i][j]=1;
                    maxlength=max(maxlength,j-i+1);
                    continue;}
                if(ispalindromic[i+1][j-1]&&s[i]==s[j]){
                    ispalindromic[i][j]=1;
                    maxlength=max(maxlength,j-i+1);
                }
            }}
        for(int i=0;i<s.length();i++){
        int j=i+maxlength-1;
            if(ispalindromic[i][j]){
                return s.substr(i,j);
            }
        }
        return s.substr(0,1);
    }
};

Я создал ispalindromic[1000][1000] и убедился, что каждый алфавит сам по себе является палиндромом c. Потом проверяю палиндроми c от длины 2 и так далее. Когда ispalindromic становится истинным, код обновляет maxlength, так что в конце код может просто использовать maxlength для печати самого длинного палиндрома c.

Ответы [ 2 ]

3 голосов
/ 05 августа 2020

Есть некоторые проблемы с этим кодом.

  1. Индексы ваших циклов for Если учесть длину l возможной подстроки, ваша l должна go между 2 на s.length(), поэтому внешний для l oop должен быть:

    for(int l=2;l<=s.length();l++){ Видите ли, я изменил l < s.length() на l <= s.length()

  2. Затем ваш i индекс внутреннего l oop должен go от 0 до s.length()-l он не может go дальше, чем тот, когда вы рассматриваете строку длиной l. Его нужно изменить как:

    for(int i=0;i<s.length()-l+1; i++){

  3. Тогда if условие для l=2 следует изменить как: 

              if(l==2){
             if ( s[i] == s[j] ) {
              ispalindromic[i][j]=1;
               maxlength=max(maxlength,j-i+1);
             }

             continue;
         }

    Вам нужно переместить s[i] == s[j] внутрь if, потому что независимо от s[i] == s[j] вам нужно продолжить в соответствии с вашим кодом.

  4. Вам нужно вывести подстроку, которая охватывает длину of maxlength, поэтому ваш оператор возврата должен быть: return s.substr(i,maxlength);

С этими исправлениями код будет: 

class Solution {
public:
    string longestPalindrome(string s) {
        int maxlength = 1;
        bool ispalindromic[1000][1000] = {false};

        for (int i = 0; i < s.length(); i++) {
            ispalindromic[i][i] = 1;
        }

        for (int l = 2; l <= s.length(); l++) {
            for (int i = 0; i < s.length() - l + 1; i++) {
                int j = i + l - 1;

                if (l == 2) {
                    if ( s[i] == s[j] ) {
                        ispalindromic[i][j] = 1;
                        maxlength = max(maxlength, j - i + 1);
                    }

                    continue;
                }

                if (ispalindromic[i + 1][j - 1] && s[i] == s[j]) {
                    ispalindromic[i][j] = 1;
                    maxlength = max(maxlength, j - i + 1);
                }
            }
        }

        for (int i = 0; i < s.length(); i++) {
            int j = i + maxlength - 1;

            if (ispalindromic[i][j]) {
                return s.substr(i, maxlength);
            }
        }

        return s.substr(0, 1);
    }
};
1 голос
/ 05 августа 2020

Не уверен, с какими проблемами вы столкнулись. Этот ответ правильный, решает ваши проблемы.

Кроме того, это также пройдет и является аналогичным методом программирования динамической c, как и ваш: 

#include <cstdint>
#include <string>

const static struct Solution {
    using SizeType = std::uint_fast16_t;
    static std::string longestPalindrome(const std::string s) {
        const SizeType slen = std::size(s);

        if (slen < 2) {
            return s;
        }

        SizeType maxlen = 0;
        SizeType head = 0;
        SizeType curr = 0;

        while (curr < slen) {
            SizeType left = curr;
            SizeType right = curr;

            while (right < slen - 1 and s[right] == s[-~right]) {
                ++right;
            }

            curr = -~right;

            while (right < slen - 1 and left > 0 and s[-~right] == s[left - 1]) {
                ++right;
                --left;
            }

            SizeType templen = -~right - left;

            if (templen > maxlen) {
                head = left;
                maxlen = templen;
            }
        }

        return s.substr(head, maxlen);
    }
};


// -~x is simply x + 1;

Ссылки

...