Leetcode Day 8 - Advanced String Manipulations & KMP
Involves more advanced string operations, such as reversing the order of words, finding the first occurrence of a substring, identifying repeated patterns, and handling right-handed string manipulations.
String
| Diff | Problem | Python | Java |
|---|---|---|---|
 | 151 Reverse Words in a String | ✅ | |
| Kama-55 Right-Handed String | ✅ |
Optional Queations about KMP
| Diff | Problem | Python | Java |
|---|---|---|---|
 | 28 Find the Index of the First Occurrence in a String | ✅ | |
| 459 Repeated Substring Pattern | ✅ |
Reverse Words in a String
Given an input string s, reverse the order of the words.
A word is defined as a sequence of non-space characters. The words in s will be separated by at least one space.
Return a string of the words in reverse order concatenated by a single space.
Note that s may contain leading or trailing spaces or multiple spaces between two words. The returned string should only have a single space separating the words. Do not include any extra spaces.
Example 1
1
2
Input: s = "the sky is blue"
Output: "blue is sky the"
Example 2
1
2
3
Input: s = " hello world "
Output: "world hello"
Explanation: Your reversed string should not contain leading or trailing spaces.
Example 3
1
2
3
Input: s = "a good example"
Output: "example good a"
Explanation: You need to reduce multiple spaces between two words to a single space in the reversed string.
Solution2
- Remove extra spaces:
the sky is blue->the sky is blue - reverse charaters:
the sky is blue->eulb si yks eht - reverse each word:
eulb si yks eht->blue is sky the
1. Remove extra spaces
- Solution 1: Traverse the String:
- Complexity: O(n2)
- Solution 2: Use double pointers to remove extra spaces
- Complexity: O(n)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
# Remove leading spaces # Remove leading spaces while(s[fast] == ' ' and fast < len(s)): fast += 1 # Remove extra spaces between words while(fast < len(s)): if not(fast - 1 > 0 and s[fast -1] == res[fast] and s[fast] == ' '): s[slow] = s[fast] slow += 1 fast += 1 # Remove trailing spaces if(slow - 1 > 0 and s[slow - 1] == ' '): s = s[:slow - 1] else: s = s[:slow]
- Solution 3: Similar to idea in 27 Remove Element:
- Complexity: O(n)
1 2 3 4 5 6 7 8 9 10 11 12 13 14
i = 0 slow = 0 while i < len(s): if (s[i] != ' '): if(slow != 0): s[slow] = ' ' slow += 1 while(i < len(s) and s[i] != ' '): s[slow] = s[i] slow += 1 i += 1 i += 1 s = s[:slow]
- Other tricky solution in python:
strip()removes the leading and trailing spaces in a string.split()splits string into a list of word.
2. Revers characters
Similar to 344 Revers String, use double pointers.
1
2
3
4
def reverseWord(s):
for i in range(len(s) // 2):
s[i], s[len(s) - i - 1] = s[len(s) - i - 1], s[i]
return s
Or Python can simply reverse the word by slicing
1
2
def reverseWord(word):
return word[::-1]
3. Reverse each word
1
2
3
4
5
start = 0
for i in range(len(s) + 1):
if i == len(s) or s[i] == ' ':
s[start:i] = reverseWord(s[start:i])
start = i + 1
Completed Solution: Python
Solution without using split()
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
class Solution(object):
def reverseWords(self, s):
s = list(s)
l = len(s)
# Remove leading spaces
i = 0
slow = 0
while i < len(s):
if (s[i] != ' '):
if(slow != 0):
s[slow] = ' '
slow += 1
while(i < len(s) and s[i] != ' '):
s[slow] = s[i]
slow += 1
i += 1
i += 1
#Resize s
s = s[:slow]
l = len(s)
#Reverse Characters
s = s[::-1]
#Reverse Words
start = 0
for i in range(l + 1):
if(i == l or s[i] == ' '):
s[start:i] = s[start:i][::-1]
start = i + 1
return ''.join(s)
Solution using split()
1
2
3
4
5
class Solution:
def reverseWords(self, s):
words = s.split()
words = words[::-1]
return ' '.join(words)
Right-Handed String
题目描述
字符串的右旋转操作是把字符串尾部的若干个字符转移到字符串的前面。给定一个字符串
s和一个正整数k，请编写一个函数，将字符串中的后面k个字符移到字符串的前面，实现字符串的右旋转操作。 例如，对于输入字符串abcdefg和整数2，函数应该将其转换为fgabcde。
输入描述
输入共包含两行，第一行为一个正整数
k，代表右旋转的位数。第二行为字符串s，代表需要旋转的字符串。
输出描述
输出共一行，为进行了右旋转操作后的字符串。
输入示例
输出示例
Solution
Python
1
2
3
4
5
k = int(input())
s = input()
s = s[len(s)-k:] + s[:len(s)-k]
print(s)
Find the Index of the First Occurrence in a String
Given two strings needle and haystack, return the index of the first occurrence of needle in haystack, or -1 if needle is not part of haystack.
Example 1
1
2
3
4
Input: haystack = "sadbutsad", needle = "sad"
Output: 0
Explanation: "sad" occurs at index 0 and 6.
The first occurrence is at index 0, so we return 0.
Example 2
1
2
3
Input: haystack = "leetcode", needle = "leeto"
Output: -1
Explanation: "leeto" did not occur in "leetcode", so we return -1.
Solution
Python
Solution 1: KMP
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution(object):
def strStr(self, haystack, needle):
l = len(needle)
if l == 0:
return 0
j = 0
prefix = [0] * l
for i in range(1,l):
while j > 0 and needle[j] != needle[i]:
j = prefix[j - 1]
if needle[j] == needle[i]:
j += 1
prefix[i] = j
j = 0
for i in range(len(haystack)):
while j > 0 and haystack[i] != needle[j]:
j = prefix[j - 1]
if haystack[i] == needle[j]:
j += 1
if j == l:
return i - l + 1
return -1
Solution 2: Use index()
1
2
3
4
5
6
class Solution(object):
def strStr(self, haystack, needle):
try:
return haystack.index(needle)
except ValueError:
return -1
Solution 3: Use find()
1
2
3
class Solution(object):
def strStr(self, haystack, needle):
return haystack.find(needle)
Similar Questions
| Diff | Similar Questions | Python | Java |
|---|---|---|---|
| 459 Repeated Substring Pattern7 | ||
 | 214 Shortest Palindrome8 |
Repeated Substring Pattern
Given a string s, check if it can be constructed by taking a substring of it and appending multiple copies of the substring together.
Example 1
1
2
3
Input: s = "abab"
Output: true
Explanation: It is the substring "ab" twice.
*Example 2
1
2
Input: s = "aba"
Output: false
Example 3
1
2
3
Input: s = "abcabcabcabc"
Output: true
Explanation: It is the substring "abc" four times or the substring "abcabc" twice.
Solution
解释后补
Python
Solution 1: KMP
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution(object):
def repeatedSubstringPattern(self, s):
j = 0
j_max = 0
prefix = [0] * len(s)
for i in range(1,len(s)):
while j > 0 and s[i] != s[j]:
j = prefix[j - 1]
if s[i] == s[j]:
j += 1
j_max = max(j,j_max)
prefix[i] = j
return (prefix[-1] != 0 and len(s) % (len(s) - prefix[-1]) == 0)
Solution 2: Use find()
1
2
3
4
5
6
class Solution(object):
def repeatedSubstringPattern(self, s):
if len(s) <= 1:
return False
ss = s[1:] + s[:-1]
return ss.find(s) != -1
Similar Questions
| Diff | Similar Questions | Python | Java |
|---|---|---|---|
| 686 Repeated String Match10 |
Reference
Leetcode-151 Reverse Words in a String: https://leetcode.com/problems/reverse-words-in-a-string/description/. ↩︎
代码随想录-翻转字符串里的单词: https://programmercarl.com/0151.翻转字符串里的单词.html. ↩︎ ↩︎2
卡码网-55 右旋字符串: https://kamacoder.com/problempage.php?pid=1065/. ↩︎
代码随想录-右旋字符串: https://programmercarl.com/kama55.右旋字符串.html. ↩︎
Leetcode-28 Find the Index of the First Occurrence in a String: https://leetcode.com/problems/find-the-index-of-the-first-occurrence-in-a-string/description/. ↩︎
代码随想录-实现 strStr(): https://programmercarl.com/0028.实现strStr.html. ↩︎
Leetcode - 459 Repeated Substring Pattern: https://leetcode.com/problems/repeated-substring-pattern/description/. ↩︎ ↩︎2
Leetcode-214 Shortest Palindrome: https://leetcode.com/problems/shortest-palindrome/description/. ↩︎
代码随想录-重复的子字符串: https://programmercarl.com/0459.重复的子字符串.html. ↩︎
Leetcode-686 Repeated String Match: https://leetcode.com/problems/repeated-string-match/description/. ↩︎