字符串

最小包含子串的长度

代码：

package org.apache.spark.scala.codeviewguide
import scala.collection.mutable
/**
 * 给定字符串str1和str2，求str1的子串中含有str2所有字符的最小子串长度。【举例】
str1=＂abcde＂，str2=＂ac＂。因为＂abc＂包含str2所有的字符，并且在满足这一条件的str1的所有子串中，＂abc＂是最短的，返回3。
str1="abcdeac", str2="ac". ret=2;
str1=＂12345＂，str2=＂344＂。最小包含子串不存在，返回0。
 */
object StringMinContainSubStr {
  def main(args: Array[String]): Unit = {
    val str = "abcdfacddd"
    val subStr = "acc"
    println(findMinContainSubStr(str, subStr))
  }
  def findMinContainSubStr(str: String, subStr : String): String = {
    val need = subStr.toCharArray
      .map((_, 1))
      .groupBy(_._1)
      .mapValues(_.foldLeft(0)(_ + _._2))
    val windows = new mutable.HashMap[Char, Int]()
    var valid = 0
    var minLen = Integer.MAX_VALUE
    var left = 0
    var right = 0
    var start = 0
    while (right < str.length) {
      // 扩大窗口找到有效值
      val ch = str.charAt(right);
      right += 1
      if (need.contains(ch)) {
        if (windows.contains(ch)) {
          windows(ch) += 1
        } else {
          windows(ch) = 1
        }
        if (windows(ch) == need(ch)) {
          valid += 1    // 有效次+1
        }
      }
      // 缩小窗口。更新可行解
      while (valid == need.size) {
        if (right - left < minLen) {
          start = left
          minLen = right - left
        }
        val ch = str.charAt(left)
        left += 1
        if (need.contains(ch)) {
          // abcdefac and acc. windows去掉第一个a其实并不影响valid值
          if (windows(ch) == need(ch)) {
            valid -= 1
          }
          windows(ch) -= 1
        }
      }
    }
    str.substring(start, start + minLen)
  }
}