2019-08-16.md

每日一题 - 字符串首尾相等的最长子串

信息卡片

• 时间：2019-08-16
• 题目链接：无
• tag：String Hash Table

题目描述

求一个字符串首尾相等的最长子串，例如abcba，最长就是abcba

参考答案

思路:

头尾两个字母相同的子串，比如abca，这里头尾相同的就是a..a子串，它的长度就是这两个a的下标之差+1；

如果是abcadefa，这里有三个a，那么这个子串的长度是第一个a和最后一个a的下标之差+1；

这时候规律就来了，那我只要计算同一个字母第一次出现和最后一次出现的位置就好了嘛，最后再求个最大值；

那这样的话，我们只要一次遍历，用一个map把这些位置记下来即可。

但是仔细想想，我存同一个字母的这么多位置，好像最后我也只取这个位置集合的第一个和最后一个啊，那我为什么还要存这么多，存起始位置就好了嘛！ 每次遍历到第2,3,4个相同字母的时候，我都减去第一个此字母位置的下标再看看这个差值是不是最大的。 所以代码来了：

JavaScript Code:

var LES = function (str) {
    var map = {}; // 用来存储遍历到的字母出现的第一个位置
    var maxLen = 1; // 初始化最大子串长度
    var substrStartIndex = 0; // 最长子串的起始位置
    for (var i = 0; i < str.length; i++) {
        var char = str[i];
        if (map[char] != null) { // 如果这个字母之前已经出现过了
            if (i - map[char] + 1 > maxLen) { // 那么计算当前这个字母到第一次出现的位置距离，然后比较
                maxLen = i - map[char] + 1;
                substrStartIndex = map[char]; // 如果是最大值，记录下当前最大子串的起始位置
            }
        } else {
            map[char] = i;// 如果这个字母之前没出现过，那么记下它的下标
        }
    }

    return str.slice(substrStartIndex, substrStartIndex + maxLen);
}

优秀解答

暂缺