极客996

极客996

  • 28文章
  • 1评论
  • 6955文章浏览

LeeCode刷题计划—— 最长/最短回文字串

public class FindMaxHWStr {

    public static void main(String[] args) {

        long startTime = System.currentTimeMillis();
        String str = "dsadsad111111111111111aab";
        System.out.println(longestPalindrome(str, true));
        System.out.println("字符长度:" + str.length());
        System.out.println("耗时ms:" + (System.currentTimeMillis() - startTime));

    }

    /**
     * @param str 检测字符串
     * @param max true >>>> 最长回文 ,  false >>>> 最短回文
     * @return
     */
    public static String longestPalindrome(String str, boolean max) {
        char[] chars = str.toCharArray();
        Map<Integer, Set<Integer>> indexMap = new HashMap<>();
        int i = 0;
        for (int s = 0; s < chars.length; s++) {
            for (int e = chars.length - 1; e >= 0; e--) {
                i++;
                if (s == e) {
                    break;
                }
                if (chars[s] == chars[e] && s != e) {
                    if (indexMap.get(s) != null) {
                        indexMap.get(s).add(e);
                    } else {
                        Set<Integer> endIndexs = new HashSet<>();
                        endIndexs.add(e);
                        indexMap.put(s, endIndexs);
                    }
                }
            }
        }

        int targetLengh = 0;
        boolean isExit = false;
        int startIndex = 0;
        int endIndex = 0;
        for (Integer index : indexMap.keySet()) {
            for (Integer end : indexMap.get(index)) {
                i++;
                String subStr = str.substring(index, end + 1);
                if (validHW(subStr.toCharArray())) {
                    int lenth = end - index;
                    if (isExit == false) {
                        isExit = true;
                        targetLengh = lenth;
                        startIndex = index;
                        endIndex = end;
                    } else {
                        if (max) {
                            if (lenth > targetLengh) {
                                targetLengh = lenth;
                                startIndex = index;
                                endIndex = end;
                            }
                        } else {
                            if (lenth < targetLengh) {
                                targetLengh = lenth;
                                startIndex = index;
                                endIndex = end;
                            }
                        }
                    }
                }
            }
        }
        System.out.println("遍历次数:" + i);
        return str.substring(startIndex, endIndex + 1);
    }

    public static boolean validHW(char[] chars) {
        for (int i = 0; i <= chars.length / 2; i++) {
            if (chars[i] != chars[chars.length - (i + 1)]) {
                return false;
            }
        }
        return true;
    }
}

Rick  13  2021-06-03 阅读全文