LeetCode | 字符串组学习12.29--01.03

• LeetCode 344.Reverse String

Write a function that takes a string as input and returns the string reversed.
Example 1:
Input: "hello"
Output: "olleh"

 class Solution{
    public String reverseString(String s){
        int left = 0;
        int right = s.length()-1;
        char[] ch = s.toCharArray();
        while(left < right){
            Swap(ch,left,right);
            left++;
            right--;
        }
        return new String(ch);
    }

    public void swap(char[] ch,int left,int right){
        char temp = ch[left];
        ch[left] = ch[right];
        ch[right] = temp;
    }
}

• Leetcode 557.Reverse Words in a String III

Given a string, you need to reverse the order of characters in each word within a sentence while still preserving whitespace and initial word order.
Example 1:
Input: "Let's take LeetCode contest"
Output: "s'teL ekat edoCteeL tsetnoc"
Note: In the string, each word is separated by single space and there will not be any extra space in the string.

调用函数的写法：

class Solution {
    public String reverseWords(String s) {
        String[] StringAfterSplit = s.split(" ");
        StringBuilder builder = new StringBuilder();
        for(int i = 0; i<StringAfterSplit.length;i++){
            builder.append(new StringBuilder(StringAfterSplit[i]).reverse().toString()+" ");
        }
        return builder.toString().trim();
    }
}

常规面试写法(不让用reverse())：

class Solution{
    public String reverseWords(String s){
        StringBuilder builder = new StringBuilder();
        String[] split = s.split(" ");
        for(int i = 0; i<split.length;i++){
            String str = split[i];
            char[] ch = str.toCharArray();
            int front = 0;
            int tail = ch.length-1;
            while(tail>front){
                char temp = ch[front];
                ch[front] = ch[tail];
                ch[tail] = temp;
                front++;
                tail--;
            }
            builder.append(new String(ch)+(i == split.length-1?"":" "));
        }
        return builder.toString();
    }
}

• Leetcode 20.Valid Parentheses

Given a string containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.
An input string is valid if:
Open brackets must be closed by the same type of brackets.
Open brackets must be closed in the correct order.
Note that an empty string is also considered valid.
Example 1:
Input: "()"
Output: true

    public String isValid(String s){
        char[] ch = s.toCharArray();
        Stack<Character> stack = new Stack<Character>();
        for(int i = 0;i < ch.length;i++){
            if(stack.size == 0){
                stack.push(ch[i]);
            }else if((ch[i]==')'&&stack.peek()=='(')||
                     (ch[i]==']'&&stack.peek()=='[')||
                     (ch[i]=='}'&&stack.peek()=='{')){
                stack.pop();
            }else stack.push(ch[i]);
        }
        return stack.size()==0;
    }
}

• Leetcode 14.Longest Common Prefix

Write a function to find the longest common prefix string amongst an array of strings.
If there is no common prefix, return an empty string "".
Example 1:
Input: ["flower","flow","flight"]
Output: "fl"
Example 2:
Input ["dog","racecar","car"]
Output: ""
Explanation: There is no common prefix among the input strings.
Note:
All given inputs are in lowercase letters a-z.

class Solution {
    public String longestCommonPrefix(String[] strs) {
        if (strs.length == 1){
            return strs[0];
        }
        if(strs.length == 0){
            return "";
        }
        StringBuilder builder = new StringBuilder();
        if(strs.length > 1){
            int len = strs[0].length();
            for(int i = 0;i<len;i++){
                char curr = strs[0].charAt(i);  //依次指向第一个字符串的第i个字符
                for(int j = 1;j<strs.length;j++){//依次遍历第二到第n个字符串
                    if(strs[j].length()<=i||strs[j].charAt(i)!=curr){ //如果字符串不匹配了
                        return builder.toString();
                    }
                    if(strs[j].charAt(i) == curr && j == strs.length-1){//如果每一个字符都相等
                        builder.append(curr);
                    }
                }
            }
        }
        return builder.toString().trim();
    }
}