[LeetCode] 459. Repeated Substring Pattern

轉自LeetCode

Given a non-empty string check if it can be constructed by taking a substring of it and appending multiple copies of the substring together. You may assume the given string consists of lowercase English letters only and its length will not exceed 10000.

Example 1:

Input: "abab"

Output: True

Explanation: It's the substring "ab" twice.

Example 2:

Input: "aba"

Output: False

Example 3:

Input: "abcabcabcabc"

Output: True

Explanation: It's the substring "abc" four times. (And the substring "abcabc" twice.)

<Solution>

目前看到這篇的解法最簡明

概念就是，如果字串 s 真的是由 substr 重復組合成的

那麼 s 的第一個字就是 substr 的第一個字

s 的最後一個字就是 substr 的最後一個字

令 s1 = s + s，並且把 s1 的第一個字和最後一個字拿掉後

則 s 一定會是 s1 的 substr

code 如下

C++

	class Solution {
	public:
	bool repeatedSubstringPattern(string s) {
	if (s.empty()) {
	return false;
	}
	string ss = s + s;
	ss.erase(0,1);
	ss.pop_back();
	return ss.find(s) != string::npos;
	}
	};

view raw repeatedSubstrPattern.cpp hosted with ❤ by GitHub

Java

	class Solution {
	public boolean repeatedSubstringPattern(String s) {
	if(s.isEmpty()) {
	return false;
	}
	String ss = s.concat(s).substring(1, s.length() * 2 - 1);
	return ss.contains(s);
	}
	}

view raw repeatedSubstrPattern.java hosted with ❤ by GitHub

Kotlin

	class Solution {
	fun repeatedSubstringPattern(s: String): Boolean {
	val ss = (s + s).substring(1, s.length*2-1)
	return ss.contains(s)
	}
	}

view raw repeated_substring_pattern.kt hosted with ❤ by GitHub