关于java:Java面试手册算法篇给定一个非空字符串最多删除一个字符判断是否能成为回文字符串

25次阅读

共计 1643 个字符，预计需要花费 5 分钟才能阅读完成。

回文字符串 是指一个字符串从左到右与从右到左遍历失去的序列是雷同的。也就是说不论从左读，还是从右读，都是一样的。

比方“abcba”、“aaa”是回文字符串，而“abca”不是回文字符串，然而从 “abca” 中删除一个 b 或 c 失去的新字符串 “aca” 或 “aba” 就是回文字符串。

实现思路：

采纳首尾双向循环（双指针）形式，当遇到字符不雷同的时候，分为两种状况
- 删除左侧的一个字符（相当于左指针向右挪动一位），而后比拟和右指针组成的子串是否为回文字符串即可；
- 删除右侧的一个字符（相当于右指针向左挪动一位），而后比拟和左指针组成的子串是否为回文字符串即可；

示例代码 1 — while 循环：

    private static boolean isPalindrome(String str) {if (str == null) {return false;}
        
        int left = 0;
        int right = str.length() - 1;
        while (left < right) {if (str.charAt(left) != str.charAt(right)) {return isPalindrome(str, left + 1, right) || isPalindrome(str, left, right - 1);
            }
            left++;
            right--;
        }

        return true;
    }

    /**
     * 比拟子串是否为回文字符串
     * @param str
     * @param left
     * @param right
     * @return
     */
    private static boolean isPalindrome(String str, int left, int right) {if (str == null) {return false;}
        
        while (left < right) {if (str.charAt(left) != str.charAt(right)) {return false;}
            left++;
            right--;
        }

        return true;
    }

因为最多只能删除一个字符，当遇到第一个不雷同的字符时，再比拟最多两次即可，下面的实现是采纳 while 循环的形式，也能够采纳 for 形式来实现。

示例代码 2 — for 循环

    private static boolean isPalindrome(String str) {if (str == null) {return false;}

        char[] chars = str.toCharArray();
        for (int left = 0, right = chars.length - 1; left < right; left++, right--) {if (chars[left] != chars[right]) {return isPalindrome(chars, left + 1, right) || isPalindrome(chars, left, right - 1);
            }
        }

        return true;
    }

    private static boolean isPalindrome(char[] chars, int left, int right) {for (; left < right; left++, right--) {if (chars[left] != chars[right]) {return false;}
        }

        return true;
    }

测试验证

    public static void main(String[] args) {System.out.println(isPalindrome("abcd"));
        System.out.println(isPalindrome("abca"));
        System.out.println(isPalindrome("abcba"));
        System.out.println(isPalindrome("abcda"));
    }

输入的后果如下：