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

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

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.

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

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)

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

Method 1

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.