字符串中最长首尾相同的子字符串

深藏阁楼爱情的钟 2024-04-18 20:47 54阅读 0赞

今天本来是要练习**“给定一个字符串 `s`，找到 `s` 中最长的回文子串”**这个算法题的，但一开始理解错了意思，没有真正了解到**“回文子串”**的定义，写了一道**“字符串中最长首尾相同的子字符串”**的代码。由于这个解答使用了新的思路：**Map集合key唯一，同key的值（索引）互减求最大解得索引**，具体代码如下：

public static void main(String[] args) {
            String s = "abcda";
            longestPalindrome(s);
        }
    
        public static String longestPalindrome(String s) {
            if (s.isEmpty()) {
                return s;
            }
            char[] chars = s.toCharArray();
            int len = s.length();
            Map<Character, Integer> map1 = new HashMap<>();
            // 循环遍历正序索引存储map集合
            for (int i = 0; i < len; i++) {
                map1.put(chars[i], i);
            }
            Map<Character, Integer> map2 = new HashMap<>();
            // 循环遍历倒序索引存储map集合
            for (int i = len - 1; i >= 0; i--) {
                map2.put(chars[i], i);
            }
            int temp = 0, lindex = 0, rindex = 0;
            for (int i = 0; i < len; i++) {
                if (temp < map1.get(chars[i]) - map2.get(chars[i])) {
                    rindex = map1.get(chars[i]);
                    lindex = map2.get(chars[i]);
                    temp = rindex - lindex;
                }
            }
            return s.substring(lindex, rindex) + s.charAt(rindex);
        }

发表评论取消回复

表情：

评论列表（有 0 条评论，54人围观）

还没有评论，来说两句吧...

相关阅读

相关字符串中最长首尾相同的子字符串

天本来是要练习**“给定一个字符串 `s`，找到 `s` 中最长的回文子串”**这个算法题的，但一开始理解错了意思，没有真正了解到**“回文子串”**的定义，写了一道**...

深藏阁楼爱情的钟/ 2024年04月18日 20:47/ 0 赞/ 55 阅读

相关找出字符串中最长的回文子字符串算法

找出字符串中最长的回文子字符串算法回文字符串是指正向和反向读取都相同的字符串。在给定一个字符串的情况下，我们希望找到其中最长的回文子字符串。本文将介绍一种用Java实现的算

ゝ一纸荒年。/ 2023年10月15日 15:26/ 0 赞/ 48 阅读

相关最长的交替字符串_最长的交替子序列

最长的交替字符串 Problem statement: 问题陈述： Given a sequence of numbers you have to find out th

拼搏现实的明天。/ 2023年03月05日 11:58/ 0 赞/ 7 阅读

相关【字符串】最长不含重复字符的子字符串

1. 题目描述题目链接：[最长不含重复字符的子字符串][Link 1] ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdG

水深无声/ 2022年11月26日 07:59/ 0 赞/ 168 阅读

相关获取两个字符串中最大的相同子串

public class Demo{ //获取两个字符串中最大的相同子串，比如str1="abcwerthelloyuiodef",str2="abcw

小咪咪/ 2022年08月13日 17:37/ 0 赞/ 170 阅读

相关获取两个字符串中最大相同子串

package test; /\\ \ @author: Avery \ @description: 获取两个字符串中最大相同子串 \ @date: 2017年7

以你之姓@/ 2022年06月12日 02:15/ 0 赞/ 157 阅读

相关数据结构 - 字符串 - 最长公共子序列 + 最长公共子字符串 - 动态规划

最长公共子序列 ![最长公共子序列][SouthEast] / 最长公共子序列参考链接：http://blog.csdn.net/bi

谁践踏了优雅/ 2022年06月01日 02:42/ 0 赞/ 189 阅读

相关字符串中连续最长重复子串

使用后缀数组的概念。 include <stdio.h> include <stdlib.h> include <string.h>

一时失言乱红尘/ 2022年05月30日 03:56/ 0 赞/ 213 阅读

相关寻找一个字符串中的最长的重复子串

问题:求一个字符串中的最长的重复子串 import java.util.; / 寻找一个字符串中的最长的重复子串 / public class S

拼搏现实的明天。/ 2022年05月14日 07:19/ 0 赞/ 230 阅读

相关获取两个字符串中最大相同子串。

获取两个字符串中最大相同子串。比如： str1 = "abcwerthelloyuiodef“;str2 = “cvhellobnm” 提示：将短的那个串进行长

冷不防/ 2022年03月02日 06:00/ 0 赞/ 203 阅读