【算法训练-字符串 一】【子串问题】最长无重复子串、最长回文子串、最长公共前缀

class Solution {
    public int lengthOfLongestSubstring(String s) {
       // 1 判断入参是否为空列表
        if (s.length() == 0) {
            return 0;
        }
        // 2 定义返回结果最大值和左右指针以及滑动窗口集合
        int max = 0;
        int left = 0;
        int right = 0;
        Set<Character> set = new HashSet<>();
        // 3 滑动窗口移动并在无重复时计算最大值
        while (left < s.length() && right < s.length()) {
            // 1 无重复，右指针继续移动，重新计算最大值
            if (!set.contains(s.charAt(right))) {
                set.add(s.charAt(right++));
                max = Math.max(max, right - left);
            } else {
                // 2 有重复，左指针继续移动，直到将重复元素移出集合
                set.remove(s.charAt(left++));
            }
        }
        return max;
    }
}

import java.util.*;
public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param s string字符串
     * @return int整型
     */
    public String longestPalindrome(String s) {
        // 1 边界条件判断
        if (s.length() < 2) {
            return s;
        }
        // 2 初始化参数，结果参数的第一位存储起始位置，第二位存储长度
        int maxLength = 0;
        int[] result = new int[2];
        // 3
        for (int i = 0; i < s.length(); i++) {
            // 中心位置奇数情况下扩展结果
            int[] odd = centerSpread(s, i, i);
            // 中心位置偶数情况下扩展结果
            int[] even = centerSpread(s, i, i + 1);
            // 当前中心位置最大子串
            int[] curMax = odd[1] > even[1] ? odd : even;
            // 当前中心位置最大子串如果大于历史记录最大子串则暂存最大值及预期返回结果
            if (curMax[1] > maxLength) {
                maxLength = curMax[1];
                result = curMax;
            }
        }
        // 截取返回结果，本来如果起点是1，长度是2，那么结尾下标应该2（1+2-1），这里结尾为1+2=3，是因为3不会被计入，因为substring左闭右开区间，所以计算为（1+2-1+1（为开区间+1）=1+2=3）
        return s.substring(result[0], result[0] + result[1]);
    }
    // 扩散的核心方法
    public int[] centerSpread(String s, int left, int right) {
        // 双指针在边界内，且满足扩散条件
        while (left >= 0 && right <= s.length() - 1  &&
                s.charAt(left) == s.charAt(right)) {
            left--;
            right++;
        }
        // 回文子串为左右指针开区间内的部分：right-1-(left+1)+1=right-left-1
        return new int[] {left + 1, right - left - 1};
    }
}

import java.util.*;
public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param strs string字符串一维数组
     * @return string字符串
     */
    public String longestCommonPrefix (String[] strs) {
        // 1 入参判断，如果数组列表为空，则返回空
        if (strs.length <= 0) {
            return "";
        }
        // 2 初始化第一个字符串为最长公共前缀
        String commonPrefix = strs[0];
        for (int i = 1; i < strs.length; i++) {
            // 两两比较字符串，更新最长公共前缀
            commonPrefix = twoStrLongestCommonPrefix(commonPrefix, strs[i]);
            // 如果最长公共前缀为"",则停止比较，返回""
            if(commonPrefix==""){
                return "";
            }
        }
        return commonPrefix;
    }
    // 比较两个字符串的最长公共前缀
    private String twoStrLongestCommonPrefix(String str1, String str2) {
        // 1 定义下标及下标最大移动范围
        int index = 0;
        int maxLength = Math.min(str1.length(), str2.length());
        // 2 下标移动两两比较字符串对应字符，只要在索引范围内且字符相同就继续移动
        while (index < maxLength && str1.charAt(index) == str2.charAt(index)) {
            index++;
        }
        // 3 返回两个子串的最长公共前缀
        return str1.substring(0, index);
    }
}