LeetCode Day8 String Part.2

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.