2022/04/09

Leetcode Note: Go - Longest Palindromic Substring

Longest Palindromic Substring - LeetCode
https://leetcode.com/problems/longest-palindromic-substring/

  • Go 言語で取り組んだメモ

所感

  • 全然わからん
  • ループ回しつつ前後の要素を比較していく？

実装準備

func longestPalindrome(s string) string {
    return "hello"
}

func main() { 
    s := "babad"

    fmt.Println(longestPalindrome(s))
}

Solution

Longest Palindromic Substring - LeetCode
https://leetcode.com/problems/longest-palindromic-substring/solution/

  • Approach 1: 最長の共通文字列
    • よくある間違いが、文字列を反転して比較するという方法
      • Input 内容によっては期待通りに動作するが、完全ではない
        • 動作する例: caba という Input なら、反転すると abac となり aba が導き出せる
        • 動作しない例: abacdfgdcaba という Input なら、反転すると abacdgfdcaba となり一致するのは abacd となるが、正しくは aba
          • つまり、文字列の中に逆コピー文字列が存在する場合、このアルゴリズムが想定通りに動作しないという問題がある
      • これを改善するために、最長の共通文字列候補を見つけるたびに、部分文字列のインデックスが逆部分文字列の元インデックスと同じかを確認すれば良さそう
        • 同じなら、これまでに見つかった最長の共通文字列を更新
        • 異なるなら、スキップして次の候補を探す
      • これにより O(n^2) スペースを使用する O(n^2) 動的計画法が得られる
  • Approach 2: 総当り
    • substring の全ての可能な開始位置と終了位置を選択して、回文か判定する
  • Approach 3: 動的計画法
    • 回文を検証しながら、不要な再計算を回避してく
  • Approach 4: 中央付近の展開
    • 回文の中心を仮定して、そこから中心を拡張するように回文判定を行って調査する
  • Approach 5: Manacher’s Algorithm

Approach 1 が無難そうなのでチャレンジしてみる

v1

func Reverse(s string) string {
	runes := []rune(s)
	for i, j := 0, len(runes)-1; i < j; i, j = i+1, j-1 {
		runes[i], runes[j] = runes[j], runes[i]
	}
	return string(runes)
}

func isPalindrome(s string) bool {
    for i := 0; i < len(s); i++ {
        if string(s[i]) != s[len(s)-i-1:len(s)-i] {
            return false
        }
    }
    return true
}

func longestPalindrome(s string) string {
    reversedStr := Reverse(s)
    max := ""
    
    for i := 0; i < len(reversedStr) - 1; i++ {
        for j := i+1; j < len(reversedStr); j++ {
            currentStr := string(reversedStr[i:j])
            
            // s に reversedStr が含まれる場合
            if strings.Index(s, currentStr) != -1 {                
                // 回文判定
                // fmt.Println(currentStr)
                if isPalindrome(currentStr) == true {
                    // 最長だったら値を保持
                    if len(currentStr) > len(max) {
                        max = currentStr
                    }
                }
            }
        }
    }

    return max
}

=> Wrong Answer

  • Input が "a" の時に Output が "" 空文字になってしまう
  • Input が一文字の場合をハンドリングする処理を追加する

v2

func Reverse(s string) string {
	runes := []rune(s)
	for i, j := 0, len(runes)-1; i < j; i, j = i+1, j-1 {
		runes[i], runes[j] = runes[j], runes[i]
	}
	return string(runes)
}

func isPalindrome(s string) bool {
    for i := 0; i < len(s); i++ {
        if string(s[i]) != s[len(s)-i-1:len(s)-i] {
            return false
        }
    }
    return true
}

func longestPalindrome(s string) string {
    reversedStr := Reverse(s)
    max := ""
    
    if len(reversedStr) == 1 {
        return s
    }
    
    for i := 0; i < len(reversedStr) - 1; i++ {
        for j := i+1; j < len(reversedStr); j++ {
            currentStr := string(reversedStr[i:j])
            
            // s に reversedStr が含まれる場合
            if strings.Index(s, currentStr) != -1 {                
                // 回文判定
                // fmt.Println(currentStr)
                if isPalindrome(currentStr) == true {
                    // 最長だったら値を保持
                    if len(currentStr) > len(max) {
                        max = currentStr
                    }
                }
            }
        }
    }

    return max
}

=> Wrong Answer

  • Input が "bb" の時に Output が "b" 空文字になってしまう
  • 長さが偶数の文字列を回文判定できてない？

v3

func Reverse(s string) string {
	runes := []rune(s)
	for i, j := 0, len(runes)-1; i < j; i, j = i+1, j-1 {
		runes[i], runes[j] = runes[j], runes[i]
	}
	return string(runes)
}

func isPalindrome(s string) bool {
    for i := 0; i < len(s); i++ {
        if string(s[i]) != s[len(s)-i-1:len(s)-i] {
            return false
        }
    }
    return true
}

func longestPalindrome(s string) string {
    reversedStr := Reverse(s)
    max := ""
    
    for i := 0; i < len(reversedStr); i++ {
        for j := i+1; j <= len(reversedStr); j++ {
            currentStr := string(reversedStr[i:j])

            // s に reversedStr が含まれる場合
            if strings.Index(s, currentStr) != -1 {

                // 回文判定
                // fmt.Println(currentStr)
                if isPalindrome(currentStr) == true {
                    // 最長だったら値を保持
                    if len(currentStr) > len(max) {
                        max = currentStr
                    }
                }
            }
        }
    }

    return max
}

=> Time Limit Exceeded

  • for loop の条件が不正確だったので修正したが・・・
  • Input として "ababababababa...." のように長い文字列を指定された場合に、制限時間オーバーとなってしまった…
  • そもそも、この実装だと n^2 くらいの計算量が必要なので、ループを回しすぎている感じがある
  • 根本的に計算量が少ないアルゴリズムへの修正が必要であり、特にアイディアも出ないのでギブアップ

回答

Simple go solution (0ms) - LeetCode Discuss
https://leetcode.com/problems/longest-palindromic-substring/discuss/1255231/Simple-go-solution-(0ms)

読みづらいので Format

func longestPalindrome(s string) string {
	if len(s) == 0 || len(s) == 1 {
		return s
	}
	lStart, maxLen := 0, 1
	for i := 0; i < len(s); {
		if len(s)-i <= maxLen/2 {
			break
		}
		// skip duplicates
		k, j := i, i
		for k < len(s)-1 && s[k] == s[k+1] {
			k++
		}
		// expand around centre
		i = k + 1
		for k < len(s)-1 && j > 0 && s[k+1] == s[j-1] {
			k++
			j--
		}
		newLen := k - j + 1
		if newLen > maxLen {
			maxLen = newLen
			lStart = j
		}
	}
	return s[lStart : lStart+maxLen]
}
  • 長さが 0 or 1 なら、そのまま return
  • lStart:
    • 初期値 0
    • 最終的に、回文の最長文字列を指定する、開始位置のインデックスになる
  • maxLen:
    • 初期値 1
    • 最終的に、回文の最長文字列を指定する、文字列の長さになる
  • for loop
    • i の初期値を 0 として、 len(s) より小さい間ループする、ステップごとに i++ は行わない
    • len(s) - i が maxLen / 2 以下なら break
      • これは既存の最長文字列候補よりも小さい値については、無駄な処理が発生するため、その脚切りを行うための実装に見える
    • skip duplicates
      • k < len(s)-1 AND s[k] == s[k+1]
      • k がループ範囲 かつ 重複文字 をチェック
      • true なら重複文字を判定する範囲を広げていく
    • expand around centre
      • i = k + 1 が実質 i++
      • for loop
        • k < len(s)-1 AND j > 0 AND s[k+1] == s[j-1]
        • k がループ範囲 かつ j が 0 を超える大きさ かつ 回文を判定
        • true なら k++, j-- で回文判定する範囲を広げていく
    • newLen
      • k - j + 1
      • 回分文字列の長さ
      • maxLen より大きければ、最大の値として新しい maxLen とする
    • return
      • s[lStart : lStart+maxLen] で回文の最長文字列が表現できる

Solution での Approach 4: 中央付近の展開 な解放。うーん難しい