讨论/《春招冲刺班 - 7 天刷题挑战》 - 5. 最长回文子串/
《春招冲刺班 - 7 天刷题挑战》 - 5. 最长回文子串
共 6 个回复

1 遍历 以每个字符为中心 进行验证 注意包括 baab 和 bab 两种奇偶方式的回文
111.png

class Solution {
public:

	bool Check(const string& s, int l, int r) {
		while (l < r) {
			if (s[l] != s[r]) return false;
			l++; r--;
		}

		return true;
	}

	string longestPalindrome(string s) {
		int l = 0; int r = s.size() - 1;
		string ans;  ans += s[0];
		for (int i = 0; i < s.size(); i++) {
			for (int j = i + 1; j < s.size(); j++) {
				if (Check(s, i, j) == true) {
					if (j - i + 1 > ans.size()) {
						ans = s.substr(i, j - i + 1);
					}
				}
			}
		}

		return ans;
	}
};

2 动态规划 dp[i][j] 为范围i到j的回文,那么我们判断加入元素[i] [j]相等 也是回文
222.png

class Solution {
public:
	vector<vector<int>> dp;
	string ans;
	int ansl = 0; int ansr = 0;
	void initDp(const string& s)
	{
		dp = vector<vector<int>>(s.size() + 10, vector<int>(s.size() + 10));
		for (int i = 0; i < s.size(); i++) {dp[i][i] = 1;}

		for (int i = 0; i < s.size() - 1; i++) {
			int l = i - 1; int r = i + 1;
			while (l >= 0 && r < s.size() && s[l] == s[r]) {
				if ((r - l) > (ansr - ansl)) { ansr = r; ansl = l; }
				dp[l][r] = 1;  l--; r++;
			}
			l = i - 1; r = i + 2;
			if (s[i] == s[i + 1]) {
				if (ansl == ansr) { ansr = i + 1; ansl = i; }
				dp[i][i + 1] = 1;
			}
			while (l >= 0 && r < s.size() && s[l] == s[r] && s[i] == s[i + 1]) {
				if ((r - l) > (ansr - ansl)) { ansr = r; ansl = l; }
				dp[l][r] = 1; l--; r++;
			}
		}
	}


	string longestPalindrome(string s) {
		initDp(s);
		ans = s.substr(ansl, ansr - ansl + 1);
		return ans;
	}
};

我的视频空间

2

C++,动态规划,
828ms 击败 26.89%,
377MB 击败 22.20%,
应该和双指针暴力解复杂度差不多…… O(n2)O(n^2)

class Solution {
public:
    string longestPalindrome(string s) {
        int n = s.size();
        string ans = "";  // 初始化返回值
        vector<vector<int>> dp(n, vector<int>(n));  // 初始化 dp 储存
        for (int l = 0; l < n; ++l) {
            for (int i = 0; i + l < n; ++i) {
                int j = i + l;
                if (l == 0) {  // 边界条件 1
                    dp[i][i] = 1;  // 将单个字母都预设为真回文
                } else if (l == 1) {  // 边界条件 2
                    dp[i][j] = (s[i] == s[j]);  // 连续两个相同字母也是回文
                } else {
                    dp[i][j] = ((s[i] == s[j]) && dp[i+1][j-1]);  // 回文的递归定义
                }
                if (dp[i][j] && (l + 1 > ans.size())) {  // 如果 dp[i][j] 是回文且比目前的答案更优
                    ans = s.substr(i, l + 1);
                } 
            }
        }
        return ans;
    }
};

提供一种不需要判断奇数和偶数位置的中心匹配算法【Java运行只需4ms】,
先上代码:

public String longestPalindrome(String s) {
        if(s == null || s.length() < 2) return s;

        int len = s.length();
        int begin = 0, maxlen = 0;                      //记录最长回文子串的起始下标和长度
        char[] chs = s.toCharArray();                   //转化为字符数组
        int count = 1;                                  //记录“中间位置”的长度
        //如果中间位置是一段,那么跳过所有相等的字符
        for(int i=0; i<len-1; i += count){              //从字符串的每个位置扩散找最长回文串
            int left = i, right = i;
            //首先找到“中间位置”,也就是所有字符都相等的一段,可能是1个,也可能不止一个
            while(--left > -1 && chs[left] == chs[i]);  //先向左找到和当前位置相等的最左端
            while(++right < len && chs[right] == chs[i]);//然后向右找到和当前位置相等的最右端
            
            count = right - left - 1;                   //计算“中间位置”的长度
            //向两端扩散
            while(left > -1 && right < len){                
                if(chs[left] == chs[right]){            //两端相等则继续扩散
                    --left; ++right;
                }else{                                  //不相等则立刻跳出循环
                    break;
                }
            }
            if(right - left - 1 > maxlen){              //记录当前最长回文子串的起始索引和长度
                begin = left+1;
                maxlen = right - left -1;
            }
        }
        return s.substring(begin, begin+maxlen);
}

具体思路:

  • 由于题目要求找回文子串,那么根据回文串的特点,只要从中间位置开始,分别用左右两个指针来向左右扩散判断,例如:
  • 对于 abcba ,只要从中间的 c 【下标为2】开始,分别向两边扩散判断【left=1,right=3】,发现都是b,相等,再扩散,发现都是a,又相等,最终就能知道这是一个回文串,
  • 但是,如果字符串是 abba ,怎么扩散呢?
  • 所以,想个办法,让这个“中间位置”不仅仅是1个位置,而是一段长度,
  • 比如 abba 这时候中间位置就是 bb; 又比如 adcbbbbcda 这时候中间位置就是 bbbb,
  • 所以先找到“中间位置”【可能是1个字符,也可能不止一个字符】,然后再向两边扩散判断就可以了;
  • 最后要注意,由于“中间位置”是一段,那么对于重复的字符,就不需要再次遍历,例如:
  • acbbbca ,当循环到i=2【即第一个b时】,中间位置是bbb那么下一次直接从c开始判断就可以了,不需要再判断第二个和第三个b,这样可以大大减少判断次数。
  • 具体代码思路见注释

遍历以每一个值为中心的回文有多长,更新最大值
通过返回值去掉重复的数
代码如下:

class Solution {
    public String longestPalindrome(String s) {
        if(s == null || s.length() == 0)
            return "";
        int[] range = new int[2];
        char[] str = s.toCharArray();
        for(int i = 0; i < s.length(); i++)
            i = findLongest(str, i, range);
        return s.substring(range[0], range[1] + 1);
    }
    private int findLongest(char[] str, int low, int[] range){
        int high = low;
        while(high < str.length - 1 && str[high + 1] == str[low])
            high++;
        int ret = high;
        while(low > 0 && high < str.length - 1 && str[high + 1] == str[low - 1]){
            low--;
            high++;
        }
        if(high - low > range[1] - range[0]){
            range[0] = low;
            range[1] = high;
        }
        return ret;
    }
}

中心扩散法,考虑奇数长度和偶数长度的情况

class Solution:
    def longestPalindrome(self, s: str) -> str:

        def center(l,r):
            while l >= 0 and r < len(s) and s[l] == s[r]:
                l -= 1
                r += 1
            return s[l + 1 : r] 

        n = len(s)
        ans = ""
        for i in range(n):
            x = center(i,i) #长度为奇数的情况
            if len(x) > len(ans):
                ans = x
            y = center(i,i + 1) #长度为偶数的情况
            if len(y) > len(ans):
                ans = y
        return ans

        

参与“7天刷题挑战”的童鞋欢迎点击问卷加入专属社群哦~
2月1日-7日,字节跳动工程师直播刷题等你来围观