LeetCode 5.最长回文子串 C#

2021/6/7 1:20:57

本文主要是介绍LeetCode 5.最长回文子串 C#,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

原题:https://leetcode-cn.com/problems/longest-palindromic-substring/

给你一个字符串 s,找到 s 中最长的回文子串。

示例 1:

输入:s = "babad"
输出:"bab"
解释:"aba" 同样是符合题意的答案。
示例 2:

输入:s = "cbbd"
输出:"bb"
示例 3:

输入:s = "a"
输出:"a"
示例 4:

输入:s = "ac"
输出:"a"

暴力破解法

1.首先判断是否为空

2.考虑到存在多种情况(abba;abcba;abbba)

3.左右对比

public class Solution {
    public string LongestPalindrome(string s) {
if (s == null || s.Length <= 1) //s的长度为空或1
            {
                return s;
            }

            string result = s[0].ToString();

            int max = 0;
            int maxLeft = 0;
            int maxRight = 0;

            for (int i = 1; i < s.Length; i++)
            {
                int left = i - 1;
                int right = i + 1;

                while (left >= 0) //执行0次abcba形回文判别;1次abba形回文判别;2次为abbba形判别。依次推
                {
                    if (s[left] == s[i])
                    {
                        if (i - left > max) //判断是否为最长
                        {
                            maxLeft = left;
                            maxRight = i;
                            max = i - left;
                        }
                        left--;
                        continue;
                    }
                    else
                    {
                        break;
                    }
                }

                while (left >= 0 && right < s.Length)//判断左右是否相等
                {
                    if (s[left] == s[right])
                    {
                        if (right - left > max)
                        {
                            maxLeft = left;
                            maxRight = right;
                            max = right - left;
                        }
                        left--;
                        right++;
                        continue;
                    }
                    else
                    {
                        break;
                    }
                }
            }

            if (max > 0)
            {
                result = "";
                for (int i = maxLeft; i <= maxRight; i++)
                {
                    result += s[i];
                }
            }

            return result;
    }
}

 



这篇关于LeetCode 5.最长回文子串 C#的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!


扫一扫关注最新编程教程