2021-10-16

2021-10-16 最长回文子串——暴力解法（c++）

暴力解法第一版(用的全是c++自带函数)——代码短，效率低

class Solution {
public:
    string longestPalindrome( string s ) {
        string maxString = "";	//存最长回文子串
        int maxCount = 0;	//存最长回文子串元素个数 初始都为0

		//从前往后依次循环
        for( int i = 0; i < s.length(); i++ ) {
            for( int j = i; j < s.length(); j++ ) {
                string s1 = s.substr( i, j - i + 1 );	//截取对应串
                string s2 = s1; //对应串副本
                reverse( s2.begin(), s2.end() );	//将副本反转

				//先比较长度是否大于maxCount,再比较s1是否等于s2，这样效率会高一丢丢
                if( ( s2.length() > maxCount ) && ( s1 == s2 ) ) {
                    maxString = s.substr( i, j - i + 1 );
                    maxCount = j - i + 1;
                }

            }
        }

        return maxString;
    }
};

暴力解法第二版(比较方法升级)——不能通过力扣，时间超限

class Solution {
public:
    string longestPalindrome( string s ) {
        string maxString = s.substr( 0, 1 );	//初值为第一个字符
        int maxCount = 1;
        int index = 0;	//存最长回文子串起点下标

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

				//没有了截取操作和反转操作，记录最长字串起点
                if( ( j - i + 1 ) > maxCount && ( Valid( s, i, j ) == true ) ) {
                    index = i;
                    maxCount = j - i + 1;
                }

            }
        }

        return s.substr( index, maxCount );
    }
    bool Valid( string s, int left, int right ) {
        while( left <= right ) {
            if( s[left] != s[right] ) {
                return false;
            }

            left++;
            right--;
        }

        return true;
    }
};