Illustration leetcode - 5. Longest palindrome substring (difficulty: medium)

One 、 subject

Give you a string  s, find  s  The longest palindrome substring in .

Two 、 Example

2.1> Example 1：

【 Input 】s = "babad"
【 Output 】"bab"
【 explain 】"aba" It's the same answer .

2.2> Example 2：

【 Input 】s = "cbbd"
【 Output 】"bb"

Tips ：

• 1 <= s.length <= 1000
• s  It consists only of numbers and English letters

3、 ... and 、 Their thinking

3.1> Diverge to both sides through the center point

Because this question is to find the longest palindrome string , therefore , We can take measures after determining the center point , The way to expand to both sides , To judge “ scanning ” Is the substring to palindrome , If it is , Then continue to both sides “ Expand ”, Until the palindrome condition is not met . Suppose we find a palindrome string , There are two cases of the number of characters , namely ：“ Odd number ” Number of characters and “ even numbers ” The number of characters .

about Number of odd characters , The center point is a character （ namely ：head == tail）, Then the palindrome will be written in  2*N + 1 Extend the length of . As shown in the figure below ：

about Number of even characters , The center point is two characters （ namely ：head + 1 == tail）, Then the palindrome will be written in  2*N + 2 Extend the length of . As shown in the figure below ：

Overall traversal from the beginning character to the end character , In the process of traversing , When it is found that the assembled palindrome character is the longest at this stage , Record it mid and distinct（ Palindrome character length ）, When all characters are traversed , adopt String Of substring Method to take a screenshot of a substring .

Four 、 Code implementation

4.1> Realization ： Diverge to both sides through the center point

class Solution {
    public String longestPalindrome(String s) {
        if (s == "" || s == null) {
            return null;
        }

        int mid = 0, distinct = 0;
        for (int i = 0; i < s.length(); i++) {
            int temp = Math.max(search(s, i, i), search(s, i, i + 1));
            mid = distinct < temp ? i : mid;
            distinct = Math.max(distinct, temp);
        }

        int num = (distinct % 2 == 0) ? 1 : 0; 
        return distinct == 0 ? null : s.substring(mid - distinct/2 + num, mid + distinct/2 + 1);
    }

    /**
     *  Return palindrome character length 
     *  If the return is 【 even numbers 】, shows " Center point " There are two elements , namely ：head + 1 == tail
     *  If the return is 【 Odd number 】, shows " Center point " Is an element , namely ：head == tail
     */
    public int search(String s, int head, int tail) {
        while (head >= 0 && tail < s.length() && s.charAt(head) == s.charAt(tail)) {
            head--;
            tail++;
        }
        return tail - head - 1;
    }
}

That's all for today's article ：

Writing is not easy to , An article completed by the author in hours or even days , I only want to exchange you for a few seconds give the thumbs-up & Share .

More technical dry goods , Welcome everyone to follow the official account @ Java Muse 「 Dry cargo sharing , Update daily 」

Title source ： Power button （LeetCode）