LeetCode Day8 String Part.2
Tags: leetcode, java, algorithms
Published: 2024-06-14 15:11:17

##LeetCode No.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.

 

Example 1:

Input: s = "the sky is blue"
Output: "blue is sky the"
Example 2:

Input: s = "  hello world  "
Output: "world hello"
Explanation: Your reversed string should not contain leading or trailing spaces.
Example 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.
 

Constraints:

1 <= s.length <= 104
s contains English letters (upper-case and lower-case), digits, and spaces ' '.
There is at least one word in s.
[Original Page](https://leetcode.com/problems/reverse-words-in-a-string/description/)

### Method 1
Simply the same as the reverse letter of a given String

Be careful: 
- we need to cut the blank characters like space 
- Sometimes there are several spaces continue to happen in the middle of the String

```
    public String reverseWords(String s) {
        s = s.trim();
        String[] str = s.split("\\s+");

        int left = 0;
        int right = str.length-1;

        while(left < right){
            String temp = str[left];
            str[left++] = str[right];
            str[right--] = temp;
        }
        return String.join(" ",str);
    }
```
Time: O(n) but split and loop and join, Space: O(n) String[] for O(n)





### Wrong Thought 1 Below
improve the time cut some redundant parts and we can do the swap in-place with O(n) space complexity 

Also, double vector thought can still be used.
But instead of focusing on String in String[], we can focus on letters in String 

but we need to double vector for each vector of exist double vector
like 
before: left , right
now: leftStart, leftEnd, rightStart, rightEnd 


![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/nainhp4b3dgh6g9mr012.png)

I want to remove the inner extra space and swap the first word to the last word by letters and then the second word to the second last word

** But if we do it in-place the size of 1st word may not same as the last word, it will lose information and prevent us from realizing it**

So we change our mind!

### Method 2 
we can reverse the whole String and then reverse each of the word during this process we can remove the blank characters.


---
<br>


## LeetCode No. 28. 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:

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:

Input: haystack = "leetcode", needle = "leeto"
Output: -1
Explanation: "leeto" did not occur in "leetcode", so we return -1.
 

Constraints:

1 <= haystack.length, needle.length <= 104
haystack and needle consist of only lowercase English characters.

[Original Page](https://leetcode.com/problems/find-the-index-of-the-first-occurrence-in-a-string/description/)
```
public int strStr(String haystack, String needle) {
        if(haystack.length()<needle.length()){
            return -1;
        }

        int start = 0;

        while(start<haystack.length()-needle.length()+1){
            if(haystack.charAt(start) == needle.charAt(0)){
                
                boolean hasFound = true;
                for(int i=1; i<needle.length(); i++){
                    if(! (haystack.charAt(start+i) == needle.charAt(i))){
                        hasFound = false;
                        break;
                    } 
                }

                if(hasFound){
                    return start;
                }
            }
            start++;
        }
        return -1;
    }
```
It is not a hard question:
- make a loop to traverse the haystack
- when finding the letter in the haystack same as the first letter in the needle, we start another loop to see whether the needle is the subpart of the haystack
- During this evaluation process, we also need to record the start point!
- we need a flag to evaluate whether the needle is in haystack (only evaluate all element in needle) so we need a flag
- Time O(n`m) Space O(1)

---
<br>

## LeetCode No.459. 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:

Input: s = "abab"
Output: true
Explanation: It is the substring "ab" twice.
Example 2:

Input: s = "aba"
Output: false
Example 3:

Input: s = "abcabcabcabc"
Output: true
Explanation: It is the substring "abc" four times or the substring "abcabc" twice.
[Original Page](https://leetcode.com/problems/repeated-substring-pattern/description/)

### Method 1

![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/6o2y73uakk6sgz4ever0.png)



### Method 2


```
public boolean repeatedSubstringPattern(String s) {
        if(s.length()<1){
            return false;
        }
        List<String> list = new ArrayList<>();
        int i = 1;
        while(i < s.length()){
            if(s.charAt(i) == s.charAt(0)){
                list.add(s.substring(0,i));
            }
            i++;
        }
```
```
        for(String str: list){
            int mod = s.length()%str.length();
            if(mod !=0){
                continue;
            }

            int num = s.length()/str.length();
            StringBuffer sb = new StringBuffer(str);
            for(i=0; i<num-1; i++){
                sb.append(str);
            }
            if(s.equals(sb.toString())){
                return true;
            }

        }

        return false;
    }
```
But it seems like the code is also O(m`n) time complexity.