[LeetCode] 28. Implement strStr()

轉自LeetCode

Implement strStr().

Returns the index of the first occurrence of needle in haystack, or -1 if needle is not part of haystack.

<Solution>

這題的意思就是要在 string a 裡面找到 string b，並回傳第一次出現的位置

直接比對來找就可以了

code 如下

c++

	class Solution {
	public:
	int strStr(string haystack, string needle) {
	if(needle.empty()) {
	return 0;
	}
	else if(needle.length() > haystack.length()) {
	return -1;
	}
	int haystackLen = haystack.length(), needleLen = needle.length();
	for(int i = 0; i <= haystackLen - needleLen; i++) {
	int j;
	for(j = 0; j < needleLen; j++) {
	if(haystack[i+j] != needle[j]) {
	break;
	}
	}
	if(j == needleLen) {
	return i;
	}
	}
	return -1;
	}
	};

view raw strStr_1.cpp hosted with ❤ by GitHub

kotlin

	class Solution {
	fun strStr(haystack: String, needle: String): Int {
	return when {
	needle.isEmpty() -> 0
	haystack.length < needle.length -> -1
	!haystack.contains(needle) -> -1
	else -> {
	for(i in haystack.indices) {
	if (haystack.substring(i, i+needle.length) == needle) {
	return i
	}
	}
	-1
	}
	}
	}
	}

view raw implement_strStr.kt hosted with ❤ by GitHub

也可以用 std::string 內建的 find 函式，只是比較慢

	class Solution {
	public:
	int strStr(string haystack, string needle) {
	if(needle.empty()) {
	return 0;
	}
	else if(needle.length() > haystack.length()) {
	return -1;
	}
	auto pos = haystack.find(needle);
	return (pos == string::npos) ? -1 : (int)pos;
	}
	};

view raw strStr_2.cpp hosted with ❤ by GitHub