Zenn
🤣

LeetCode 796. Rotate String

2021/11/25に公開
Kotlin
LeetCode
tech

Question

Given two strings s and goal, return true if and only if s can become goal after some number of shifts on s.

A shift on s consists of moving the leftmost character of s to the rightmost position.

For example, if s = "abcde", then it will be "bcdea" after one shift.

2つの文字列sとgoalが与えられたとき、sにいくつかのシフトを行った後にsがgoalになることができる場合に限り、trueを返します。
sのシフトとは、sの左端の文字を右端に移動することである。
例えば、s = "abcde "であれば、1回のシフトで "bcdea "になる。

Code

class Solution {
    fun rotateString(s: String, goal: String): Boolean {
        if (s.length != goal.length) return false
        val b = StringBuilder(s)
	for (char in s) {
	    b.deleteCharAt(0)
	    b.append(char)
	    if (b.toString().contains(goal)) return true
	}
	return false
    }
}

class Solution {
    fun rotateString(s: String, goal: String): Boolean {
        return s.length == goal.length && (s + s).contains(goal)
    }
}

文字列の結合においてString+Stringは都度オブジェクトを生成してしまい、オーバーヘッドとなるためStringBuilderを使いましょうというのは定石
文字列sをStringBuilderとしてコピーし、先頭の削除と末尾への追加を行いながら、
goalと一致したら終了する。

2つ目はSolutionにあったので、紹介
同じ文字列を2つくっつけると実は調べられる
スマートだとは思ったが、時間計算量がO(n^2)になってしまう。確かに
実行してみることこちらの方が成績がよかった...

Profile

  • StringBuilder

    • Runtime: 144 ms
    • Memory Usage: 33.8 MB

  • s+s.contain

    • Runtime: 140 ms
    • Memory Usage: 35.4 MB

Submission

GitHubで編集を提案

Discussion