【LeetCode】5. 最长回文子串 – Go 语言题解

导读:本篇文章讲解 【LeetCode】5. 最长回文子串 – Go 语言题解,希望对大家有帮助,欢迎收藏,转发!站点地址:www.bmabk.com


一、题目描述

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

示例 1:

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

示例 2:

输入:s = "cbbd"
输出:"bb"

提示:

1 <= s.length <= 1000
s 仅由数字和英文字母组成

二、我的题解

1. 两端向中间遍历法

设置两个指针 i , j:i 从串头开始遍历,j 从串尾往前查找。

思想:

  1. i 先指向串头,j 先指向串尾。
  2. j 从尾向头查找等于 i 所指的字符。遇到之后停下来。令临时指针 t1 、t2 指向 i 、 j 的当前位置。
  3. 然后 i++, j–,判断 i 、 j 之间的串是否回文。
  4. 如果不是回文。那么 j 从当前位置继续查找等于 i 所指的字符的字符。
  5. 如果没遇到,就 i++ ,j 再回到串尾。j 再次进行向前查找的工作。

代码:

func longestPalindrome(s string) string {

	i := 0
	j := len(s) - 1

	lenmax := 0
	strmax := ""

	var t1 int
	var t2 int

	if len(s) <= 1 {
		return s
	} else if len(s) == 2 {
		if s[i] == s[j] {
			return s
		} else {
			return s[:1]
		}
	} else {    // len(s) > 2
		for i < j {
		lab:
			for i < j && s[i] != s[j] {
				j--
			}
			if i == j {
				i++
				j = len(s) - 1
				continue
			} else {
				t1 = i
				t2 = j
				for t1 < t2 && s[t1] == s[t2] {
					t1++
					t2--
				}
				if t1 >= t2 && s[t1] == s[t2] {
                    if len(s[i:j+1]) > lenmax {
                        lenmax = len(s[i:j+1])
                        strmax = s[i:j+1]
                    }
					i++
					j = len(s) - 1
					continue
				} else if t1 < t2 && s[t1] != s[t2] {
					j--
					goto lab
				} else {
					i++
					j = len(s) - 1
					continue
				}
			}
		}

	}
    if strmax == ""{
        return s[:1]
    }else{
        return strmax
    }
		

	return ""
}

评判结果:

在这里插入图片描述

2. 后缀遍历法

思想:

  1. i 指针从前向后移动,x 指针从当前 i 指针的下一个位置向后移动。(从 x 指针开始的串可以看作是从 i 指针开始的串的后缀)
  2. 如果 x 指针遇到和 i 指针所指的字符一样的字符就停下来。令临时指针 curri 、currj 指向 i 、x 的当前位置。
  3. 然后 curri ++,currj –,判断 i 、x 之间的串是否回文。
  4. 如果不是回文。那么 x 从当前位置继续查找等于 i 所指的字符的字符。
  5. 如果没遇到,就 i++ ,再继续从步骤1开始。

代码:

func longestPalindrome(s string) string {

    lenmax := 0
    strmax := ""
    curri ,currj := 0,0
	for i , j := range s{
        for x , t := range s[i+1:]{
            if j == t{
                curri = i
                currj = x+i+1
                for curri <= currj && s[curri] == s[currj]{
                    curri++
                    currj--
                }
                if curri > currj {
                    if len(s[i:x+i+2]) > lenmax {
                         lenmax = len(s[i:x+i+2])
                         strmax = s[i:x+i+2]
                    }
                    continue
                }else{
                    continue
                }
                
            }
        }
    }
    
    if strmax == ""{
        return s[:1]
    }else{
        return strmax
    }

	return ""
}

评判结果:

在这里插入图片描述

3. 建立哈希表,遍历位置切片

将串中的每个字符与其在串中出现的所有位置的数组做一个map映射。

遍历每一个字符的位置数组。判断这些位置之间是否能组成回文串。

代码:

func longestPalindrome(s string) string {

	hash := make(map[rune][]int)

	for i, j := range s {

		if _, ok := hash[j]; ok {
			hash[j] = append(hash[j], i)
		} else {
			hash[j] = make([]int, 0)
			hash[j] = append(hash[j], i)
		}

	}
	fmt.Println(hash)

	lenmax := 0
	strmax := ""
	var t1 int
	var t2 int
	for _, v := range hash {
		for i := 0; i < len(v)-1; i++ {
			for j := i + 1; j < len(v); j++ {
				if v[j]-v[i] <= 2 {
					if len(s[v[i]:v[j]+1]) > lenmax {
						lenmax = len(s[v[i] : v[j]+1])
						strmax = s[v[i] : v[j]+1]
					}
				} else {
					t1 = v[i]
					t2 = v[j]
					for t1 < t2 && s[t1] == s[t2] {
						t1++
						t2--
					}
					if t1 >= t2 && s[t1] == s[t2] {
						if len(s[v[i]:v[j]+1]) > lenmax {
							lenmax = len(s[v[i] : v[j]+1])
							strmax = s[v[i] : v[j]+1]
						}
						continue
					} else {
						continue
					}
				}
			}

		}
	}

	if strmax == "" {
		return s[:1]
	} else {
		return strmax
	}

	return ""
}

评判结果:
在这里插入图片描述

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

文章由半码博客整理,本文链接:https://www.bmabk.com/index.php/post/118977.html

(0)

相关推荐

发表回复

登录后才能评论
半码博客——专业性很强的中文编程技术网站,欢迎收藏到浏览器,订阅我们!