LeetCode Day 08 String(1/2)

Today is first day to practice Strings.

Today started string exercises. To practice my knowledge of algorithms, forget about library functions and do the exercises in the honest way.

Question 1

344. Reverse String

Write a function that reverses a string. The input string is given as an array of characters s.

You must do this by modifying the input array in-place with O(1) extra memory.

The first question was answered with a double pointer spike in 1 minute 46 seconds

class Solution:
    def reverseString(self, s: List[str]) -> None:
        """
        Do not return anything, modify s in-place instead.
        """
        l, r = 0, len(s)-1
        while l <= r:
            s[l], s[r] = s[r], s[l]
            l += 1
            r -= 1

Question 2

541. Reverse String II

Given a string s and an integer k, reverse the first k characters for every 2k characters counting from the start of the string.

If there are fewer than k characters left, reverse all of them. If there are less than 2k but greater than or equal to k characters, then reverse the first k characters and leave the other as original.

I used a stupid method: for loop to go through the string once, and store the processed ones into the new string.

class Solution:
    def reverseStr(self, s: str, k: int) -> str:
        tab=[]
        for i in range(len(s)):
            if (i//k)%2==0:
               tab.insert(i-i%k,s[i])
            else:
                tab.append(s[i])
        res=""
        for t in tab:
            res+=t
        return res

Question 3

剑指 Offer 05. 替换空格

Implement a function that replaces each space in the string s with “%20”.

I remembered a method I used to use when I was working on a crawler: .join and split().

class Solution:
    def replaceSpace(self, s: str) -> str:
        return "%20".join(s.split(" "))

But it’s best not to use library functions, and honestly write my own.

Use the double pointer method, and create a new list, the length of the original base, every time a space is encountered, +2.

class Solution:
    def replaceSpace(self, s: str) -> str:
        counter = s.count(' ')
        
        res = list(s)
      
        res.extend([' '] * counter * 2)
        
 
        left, right = len(s) - 1, len(res) - 1
        
        while left >= 0:
            if res[left] != ' ':
                res[right] = res[left]
                right -= 1
            else:
                res[right - 2: right + 1] = '%20'
                right -= 3
            left -= 1
        return ''.join(res)

Question 4

151. 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.

This question cannot be simply reversed, then each word itself is also reversed.

There is also the possibility of encountering extra spaces, which should be dealt with first, then reversing the whole sentence, and finally restoring the word positions.

class Solution:
    def reverseWords(self, s: str) -> str:
        words = s.split()
 
        left, right = 0, len(words) - 1
        while left < right:
            words[left], words[right] = words[right], words[left]
            left += 1
            right -= 1
            
        return " ".join(words)