preface

Our community will continue to add Yi Gu (Netflix growth hacker, author of “The Way to Interview for iOS”, ACE professional fitness coach. Swift algorithm solution sorted into text version to facilitate everyone to learn and read.

We have updated 3 issues of LeetCode algorithm so far, and we will keep the update time and progress (Monday, Wednesday and Friday at 9:00 a.m.). There is not much content in each issue, so we hope you can read it on your way to work, and there will be great improvement in long-term accumulation.

Short step, no thousands of miles; No small streams, no rivers and seas, Swift community with you forward. If you have suggestions and comments welcome to leave a message at the end of the article, we will try our best to meet your needs.

Difficulty level: Medium

1. Describe

Given a string s, return the longest substring in s.

Example 2.

Example 1

Input: s = "babad" Output: "bab" Explanation: "ABA" is also a valid answer.Copy the code

Example 2

Input: s = "CBBD" Output: "bb"Copy the code

Example 3

Input: s = "a" Output: "a"Copy the code

Example 4

Input: s = "AC"Copy the code

Constraints:

  • 1 <= s.length <= 1000
  • sConsists of only numbers and letters.

3. The answer

class LongestPalindromicSubstring {
    func longestPalindrome(_ s: String) -> String {
        guard s.count > 1 else {
            return s
        }
        
        let sChars = Array(s)
        var maxLen = 0, start = 0
        
        for i in 0..<sChars.count {
            searchPalindrome(sChars, i, i, &start, &maxLen)
            searchPalindrome(sChars, i, i + 1.&start, &maxLen)
        }
        
        return String(sChars[start..<start + maxLen])
    }
    
    private func searchPalindrome(_ chars: [Character]._ l: Int._ r: Int._ start: inout Int._ maxLen: inout Int) {
        var l = l, r = r
        
        while l > = 0 && r < chars.count && chars[l] = = chars[r] {
            l - = 1
            r + = 1
        }
        
        if maxLen < r - l - 1 {
            start = l + 1
            maxLen = r - l - 1}}}Copy the code
  • Main idea: Find the longest mirror string from each index in the center.
  • Time complexity: O(n^2)
  • Space complexity: O(1)

The Github repository for this algorithm is: Leetcode-Swift

Click to go to LeetCode practice