1、有效的字母异位词

给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的字母异位词。

注意：若 s 和 t 中每个字符出现的次数都相同，则称 s 和 t 互为字母异位词

时间复杂度：$O(n)
空间复杂度：$O(n) 

import java.util.*;
class Solution {
    public boolean isAnagram(String s, String t) {
        int[] res = new int[26];
        for(char c : s.toCharArray()){
            res[c - 'a'] += 1;
        }

        for(char c : t.toCharArray()){
            res[c - 'a'] -= 1;
        }

        for(int c : res){
            if(c != 0){
                return false;
            }
        }
        return true;
    }
}

2、字母异位词分组

给你一个字符串数组，请你将 字母异位词 组合在一起。可以按任意顺序返回结果列表。

字母异位词 是由重新排列源单词的字母得到的一个新单词，所有源单词中的字母通常恰好只用一次。

时间复杂度：$O(n)
空间复杂度：$O(n) 

import java.util.*;
class Main {
    public List<List<String>> main(String[] strs) {
        Map<String,List<String>> map= new HashMap<>();
        for(String str : strs){
            char[] c =  str.toCharArray();
            Arrays.sort(c);
            String s = new String(c);
            if(!map.containsKey(s)){
                map.put(s,new ArrayList<String>());
            }
            map.get(s).add(str);
        }
        return  new ArrayList<List<String>>(map.values());
    }
}

3、找到字符串中所有字母异位词

给定两个字符串 s 和 p，找到 s 中所有 p 的 异位词 的子串，返回这些子串的起始索引。不考虑答案输出的顺序。

异位词 指由相同字母重排列形成的字符串（包括相同的字符串）。

时间复杂度：$O(n²)
空间复杂度：$O(n) 

class Main {
    public List<Integer> main(String s, String p) {
        int[] s1 = new int[26];
        int[] p1 = new int[26];
        List<Integer> res = new ArrayList<>();
        
        for(int i = 0; i < p.length(); i++){
            p1[p.charAt(i) - 'a'] += 1;
        }

        for(int left = 0,right = 0; right < s.length();right++){
            s1[s.charAt(right) - 'a'] += 1;
            if(right - left + 1 > p.length()){
                s1[s.charAt(left) - 'a'] -= 1;
                left++;
            }
            if(right - left + 1 == p.length()){
                if(isSame(s1,p1)){
                    res.add(left);
                }
            }
        }
        return res;
    }

    public boolean isSame(int[] s1,int[] p1){
        for(int i = 0; i < s1.length; i++){
            if(s1[i] != p1[i]){
                return false;
            }
        }
        return true;
    }
}

4、赎金信

 给你两个字符串：ransomNote 和 magazine ，判断 ransomNote 能不能由 magazine 里面的字符构成。如果可以，返回 true ；否则返回 false 。

magazine 中的每个字符只能在 ransomNote 中使用一次

时间复杂度：$O(n)
空间复杂度：$O(n) 

class Solution {
    public boolean canConstruct(String ransomNote, String magazine) {
            int[] res = new int[26];
            for(char c : magazine.toCharArray()){
                res[c - 'a'] += 1;
            }
            for(char c : ransomNote.toCharArray()){
                res[c - 'a'] -= 1;
                if(res[c - 'a'] < 0){
                    return false;
                }
            }

            return true;

    }
}

5、比较含退格的字符串

给定 s 和 t 两个字符串，当它们分别被输入到空白的文本编辑器后，请你判断二者是否相等。# 代表退格字符。 如果相等，返回 true ；否则，返回 false 。

注意：如果对空文本输入退格字符，文本继续为空。

时间复杂度：$O(n²)
空间复杂度：$O(n) 

class Solution {
	public boolean backspaceCompare(String s, String t) {
		return backspaceCompare2(s).equals(backspaceCompare2(t));
	}

	public String backspaceCompare2(String s){
		char[] ch = s.toCharArray();
		int slow = 0;
		int fast = 0;
        while(fast < ch.length){
			if(ch[fast] != '#'){
				ch[slow] = ch[fast];
                slow++;
			}else{
				if(slow > 0){
					slow--;
				}else{
					slow = 0;
				}
			}
            fast++;
        }
		return String.valueOf(ch,0,slow);
	}
}

6、反转字符串

编写一个函数，其作用是将输入的字符串反转过来。输入字符串以字符数组 s 的形式给出。

不要给另外的数组分配额外的空间，你必须原地修改输入数组、使用 O(1) 的额外空间解决这一问题。

时间复杂度：$O(n)
空间复杂度：$O(1) 

class main {
    public void main(char[] s) {
        if(s.length == 0 || s == null){
            return;
        }
        int left = 0;
        int right = s.length -1;
        while(left <= right){
            char temp = s[left];
            s[left] = s[right];
            s[right] = temp;
            left++;
            right--;
        }
    }
}

7、反转字符串 II

给定一个字符串 s 和一个整数 k，从字符串开头算起，每计数至 2k 个字符，就反转这 2k 字符中的前 k 个字符。

如果剩余字符少于 k 个，则将剩余字符全部反转。如果剩余字符小于 2k 但大于或等于 k 个，则反转前 k 个字符，其余字符保持原样。

时间复杂度：$O(nLogn)
空间复杂度：$O(1) 

class Solution {
    public String reverseStr(String s, int k) {
        char[] ch = s.toCharArray();
        for (int i = 0; i < ch.length; i += 2 * k){
            if(i + k - 1< ch.length){
                reverse(ch,i,i + k - 1);
                continue;

            }

            reverse(ch, i, ch.length - 1);
        }
        return new String(ch);
    }

    public void reverse(char[] ch, int i, int j){
        while(i <= j){
            char temp = ch[i];
            ch[i] = ch[j];
            ch[j] = temp;
            i++;
            j--;
        }

    }
}

8、翻转字符串里的单词

 给你一个字符串 s ，逐个翻转字符串中的所有 单词 。

单词 是由非空格字符组成的字符串。s 中使用至少一个空格将字符串中的 单词 分隔开。

请你返回一个翻转 s 中单词顺序并用单个空格相连的字符串。

class Solution {
	public String reverseWords(String s) {
		char[] ch = s.toCharArray();
		int left = 0;
		int right = ch.length - 1;
		StringBuilder sb = new StringBuilder();
		while(left < right){
            if(ch[left] == ' '){
                left++;
            }else{
                break;
            }
		}

		while(left < right){
            if(ch[right] == ' '){
                right--;
            }else{
                break;
            }
		}

		while(left <= right){
			int index = right;
			while(index >= left && ch[index] != ' '){
				index--;
			}
			for(int i = index + 1; i <= right; i++){
				sb.append(ch[i]);
			}
			if(index > left){
				sb.append(' ');
			}
			while(index >= left && ch[index] == ' '){
				index--;
			}
            right = index;
		}
		return sb.toString();
	}
}

9、反转字符串中的单词 III

 给定一个字符串，你需要反转字符串中每个单词的字符顺序，同时仍保留空格和单词的初始顺序。

时间复杂度：$O(n²)
空间复杂度：$O(n) 

class Solution {
    public String reverseWords(String s) {
        if(s.length() == 0 || s == null){
            return null;
        }

        int left = 0;
        int right = 0;
        char[] ch = s.toCharArray();
        while(right < s.length()){
            if(s.charAt(right) != ' '){
                right++;
            }else{
                reverse(ch,left,right - 1);
                right = right + 1;
                left = right;
            }
        }
        reverse(ch,left,right - 1);
        return new String(ch);
    }
    public void reverse(char[] ch, int i, int j){
        while(i <= j){
            char temp = ch[i];
            ch[i] = ch[j];
            ch[j] = temp;
            i++;
            j--;
        }
    }
}

10、整数反转

给你一个 32 位的有符号整数 x ，返回将 x 中的数字部分反转后的结果。

如果反转后整数超过 32 位的有符号整数的范围 [−231,  231 − 1] ，就返回 0。

假设环境不允许存储 64 位整数（有符号或无符号）。

时间复杂度：$O(n)
空间复杂度：$O(1) 

class Solution {
    public int reverse(int x) {
        int res = 0;
        while (x != 0) {
            int temp = x % 10;
            x = x / 10;
            if(res > Integer.MAX_VALUE / 10 || res == Integer.MAX_VALUE / 10 && temp > 7){
                return 0;
            }
            if(res < Integer.MIN_VALUE / 10 || res == Integer.MIN_VALUE / 10 && temp < -8){
                return 0;
            }           
            res = res * 10 + temp;
        }
        return res;
    }
}