go言語 再帰関数の極意

【問題】
'S'と'.'で構成された文字列がある。その文字列に対し、ある一箇所を指定するとその箇所とその両隣の文字'S'が'.'に変換される。
n回指定することができる時に、もっとも'S'を'.'に変換した時の'.'の数の最大値を求める。

（例）
入力1

1
SS.SSS

出力1

SS....
4

入力2

2
S.S.SSS

出力2

.......
7

【解答】
アルゴリズムとしては、再帰関数として全パターンを計算する。
再帰で分岐させ一つ一つの文字に対して、その箇所を指定するか、しないかで分岐させる。
呼び出しの回数に達したらreturnする。

package main

import "fmt"

func main() {
	max := 0
	str := ""
	s := "S.SS.S"
	f(s, 1, 1, &max, &str)
	fmt.Println(max, str)
}

func f(s string, tryTimes int, index int, max *int, maxS *string) {
	count := 0
	if tryTimes > 0 && index < len(s)-1 {
		f(s, tryTimes, index+1, max, maxS)
		s = s[0:index-1] + "..." + s[index+2:]
		f(s, tryTimes-1, index+1, max, maxS)
	} else {
		count = countS(s)
		if *max < count {
			*max = count
			*maxS = s
		}
	}
}

func countS(s string) int {
	count := 0
	for i := 0; i < len(s); i++ {
		if s[i] == '.' {
			count++
		}
	}
	return count
}