[LeetCode] 686. Repeated String Match

轉自LeetCode

Given two strings A and B, find the minimum number of times A has to be repeated such that B is a substring of it. If no such solution, return -1.

For example, with A = "abcd" and B = "cdabcdab".

Return 3, because by repeating A three times (“abcdabcdabcd”), B is a substring of it; and B is not a substring of A repeated two times ("abcdabcd").

Note:
The length of A and B will be between 1 and 10000.

<Solution>

想法如下

• 如果 B 要是 A 的 substring，那麼 A 的長度一定要大於等於 B

• 所以先重複Ａ，直到長度至少等於 B，檢查 B 是不是子字串

• 如果不是，再重複一次 A(當前一次的長度等於B時，還沒辦法包含所有情況)，然後檢查 B 是不是子字串

• 如果都不是，就回傳 -1

code 如下

Java(參考解答)

	class Solution {
	public int repeatedStringMatch(String A, String B) {
	int ans = 1;
	StringBuilder sb = new StringBuilder(A);
	final int len = B.length();
	for(; sb.length() < len; ans++) {
	sb.append(A);
	}
	if(sb.indexOf(B) >= 0) {
	return ans;
	}
	else if(sb.append(A).indexOf(B) >= 0) {
	return ans+1;
	}
	return -1;
	}
	}

view raw repeatedStringMatch.java hosted with ❤ by GitHub

Kotlin

	class Solution {
	fun repeatedStringMatch(a: String, b: String): Int {
	var ans = 1
	var sb = StringBuilder(a)
	while(sb.length < b.length) {
	sb.append(a)
	++ans
	}
	return when {
	sb.toString().contains(b) -> ans
	sb.append(a).toString().contains(b) -> ans + 1
	else -> -1
	}
	}
	}

view raw repeated_string_match.kt hosted with ❤ by GitHub