提供了编程的基础技术教程

zl程序教程

您现在的位置是：首页 >  其它

当前栏目

LC5.最长回文字串[通俗易懂]

通俗易懂 最长 lc5
2023-06-13 09:12:40 时间

大家好，又见面了，我是你们的朋友全栈君。

中心扩展法

主要思路是每次选一个中点，然后向两边扩展，找出以该中点对应的最长的回文串的长度，然后维护一个全局的最长回文串长度变量。

对于奇偶数长度的不同处理方式：

  • expandAroundCenter方法中如果传入同一个点的索引，则表示以该点为中心，对应着探索字符串长度为奇数的情况
  • 如果传入两个点的索引，则表示以这两个点之间为中心，对应着探索字符串长度为偶数的情况
/** * @Classname Solution5 * @Description TODO * @Date 2019/12/9 9:45 * @Created by Cheng */
public class Solution5 { 
   
    /** * 中心扩展法 * @param s * @return */
    public String longestPalindrome(String s) { 
   
        if (s == null || s.length() < 1) return "";
        int start = 0, end = 0;
        for (int i = 0; i < s.length(); i++) { 
   
            int len1 = expandAroundCenter(s, i, i);
            int len2 = expandAroundCenter(s, i, i + 1);
            int len = Math.max(len1, len2);
            if (len > end - start) { 
   
                start = i - (len - 1) / 2;
                end = i + len / 2;
            }
        }
        return s.substring(start, end + 1);
    }

    private int expandAroundCenter(String s, int left, int right) { 
   
        int L = left, R = right;
        while (L >= 0 && R < s.length() && s.charAt(L) == s.charAt(R)) { 
   
            L--;
            R++;
        }
        // 注意此时L和R都已经在有效范围外，所以长度是R-L-1
        return R - L - 1;
    }

}

马拉车

具体思路有必要单独写一篇

/** * @Classname Solution5 * @Description TODO * @Date 2019/12/9 9:45 * @Created by Cheng */
public class Solution5 { 
      
    /** * 马拉车 * @param s * @return */
    public static String longestPalindrome2(String s) { 
   
        //处理字符串
        List<Character> list = new ArrayList<>();
        for (int i = 0; i < s.length(); i++) { 
   
            list.add('#');
            list.add(s.charAt(i));
        }
        list.add('#');
        int[] dp = new int[list.size()];
        int resLen = 0;
        int resCenter = 0;
        int maxR = 0;
        int maxM = 0;

        for (int i = 1; i <list.size() ; i++) { 
   
            dp[i] = maxR>i?Math.min(dp[maxM*2-i],maxR-i):1;
            while((i-dp[i])>=0 && (i+dp[i])<list.size() && list.get(i+dp[i]) == list.get(i-dp[i]))
                dp[i]++;
            if (i + dp[i] > maxR) { 
   
                maxR = i+dp[i];
                maxM = i;
            }
            if (resLen < dp[i]) { 
   
                resLen = dp[i];
                resCenter = i;
            }
        }
        StringBuilder ret = new StringBuilder();
        for (int i = resCenter-resLen+1; i <=resCenter+resLen-1 ; i++) { 
   
            if(list.get(i)!='#')
                ret.append(list.get(i));
        }
        return ret.toString();
    }
}

发布者：全栈程序员栈长，转载请注明出处：https://javaforall.cn/164003.html原文链接：https://javaforall.cn

相关文章