LeetCode/Scala - without the firstborn of the string of characters, the longest text string back

一.引言

LeetCode There is a class of string substring problems,这里主要分析无重复字符的最长子串与最长回文子串,Summarize related methods.

二.无重复字符最长子串

1.题目要求

 给定字符串 s,Ask to find the longest substring without repetitions within a character,Note that a substring is not a subsequence.

2.Sliding pointer method

A.思路分析

通过 start 与 end Double pointer to specify the longest substring range,通过 HashMap 记录每一个 char The index of the character and implement deduplication.

-> Iterate over all strings char 字符

-> Determine whether the current character is present HashMap 中,并更新当前 start

-> end += 1,并记录当前 char 对应的索引

-> length = end - start,比较 length 与 maxLength 并更新最大长度

B.代码实现

  def solution(s: String): Int = {

    // Double pointer and indexMap
    var maxLength = 0
    var start = 0
    var end = 0

    val indexMap = mutable.HashMap[Char, Int]()

    // 转换为char
    val arr = s.toCharArray

    s.toCharArray.foreach(char => {
      if (indexMap.contains(char)) {
        start = math.max(indexMap(char), start) // 更新 start
      }
      end += 1 // 更新 end
      indexMap(char) = end
      maxLength = math.max(end - start, maxLength) // 更新 maxLength
      println(s"char: $char start: $start end: $end max: $maxLength arr: ${s.slice(start, end).mkString("")}")
    })

    maxLength
  }

为了直观,We have added log printing,以 s = "abba" 为例进行测试：

  def main(args: Array[String]): Unit = {
    val s = "abba"
    println(solution(s))
  }

Double pointers can be understood in conjunction with the execution process start 和 end 的变化. 

C.执行效率

时间复杂度 O(n),其中 n 为字符串的长度,即 char 的数量,空间复杂度为 O(|∑|),其中 ∑ A deduplication set for the current string,The normal case can be approximated as O(n),极端情况例如 s="11111" 则退化为 O(1).

三.最长回文子串

1.题目要求

给定字符串 s,Find its longest palindrome substring,Here is an explanation of what a palindrome is,That is, positive and negative strings,例如 aabbaa,aba,ccccc Both are palindromic substrings,Note that the longest non-repeating substring returns the length of the string whereas this example returns the string.

2.中心扩展法

A.思路分析

First clarify the transition conditions for palindromic characters,假设 P(i,j) 为回文子串,如果 i-1,j+1 The corresponding position elements are the same,则 P(i-1, j+1) 也是回文子串,如此类推.

-> 初始化 maxLeft,maxRight Record the interval of the longest palindrome,初始化 maxLength 记录最长长度

-> Traverse the array array index,Explore to the left,当前索引为 mid,Then the left side is mid - 1,如果 s(mid) = s(left) 则 P(left, mid) 构成回文子串,left -=1 Continue to explore left 

-> Explore to the right,方法同上,right = mid + 1,判断 s(mid) 与 s(right)

-> 向Expanded on both sides,One-way expansion mainly looks for AND mid Elements with the same elements,例如 a -> aaa,Bilateral is mainly to find the same elements on both sides,例如 aaa -> baaab,判断 s(left) = s(right)

-> 更新 maxLeft,maxRight Record the current longest palindrome range

B.代码实现

  // 中心扩展算法
  def solution(s: String): String = {

    var length = 1
    // 从每个 mid 开始向两边扩散
    var maxLeft = 0 // 起点
    var maxRight = 0 // 终点
    var maxLength = 0 // 最长回文串长度

    val arr = s.toCharArray

    arr.indices.foreach(mid => {

      var left = mid - 1
      var right = mid + 1

      // Expand to the left
      while (left >= 0 && arr(left).equals(arr(mid))) {
        left -= 1
        length += 1
      }

      // Expand to the right
      while (right <= arr.length - 1 && arr(right) == arr(mid)) {
        right += 1
        length += 1
      }

      // 向Expanded on both sides
      while (left >= 0 && right <= arr.length - 1 && arr(left) == arr(right)) {
        left -= 1
        right += 1
        length += 2
      }

      // 更新
      if (length > maxLength) {
        maxLeft = left
        maxRight = right
        maxLength = length
      }

      length = 1
    })

    println(maxLeft, maxRight, maxLength)

    s.substring(maxLeft + 1, maxRight)
  }

分别向左,右,Expanded on both sides,The last update interval,You can refer to the above analysis,After the judgment is equal,继续 left -= 1 寻找下一个 left,So the final satisfied left boundary is realLeft = maxLeft + 1,maxRight 同理,maxRight = realRight + 1,所以最终结果 subString(maxLeft + 1,maxRight).

C.执行效率

Ou a handful,Not sure how this commit ran so fast,算法时间复杂度 O(n^2),因为遍历 n 个字符,Each character expands left and right,空间复杂度 O(1).

四.总结

It can be seen that many algorithms are used 双指针、HashMap,It is therefore important to understand their common usage and boundary conditions,The second palindrome is due to P(i,j) 向 P(i-1,j+1) transfer status,Also applies to dynamic programming,There will be time to sort out dynamic programming later.