字符串问题

1.[Minimum Window Substring]https://leetcode.com/problems/minimum-window-substring/description/
solution:同样是利用HashMap来存Dict，key保存word，value保存word出现的次数(要查找的串)。然后来遍历整个母串。因为这里是要求最短的包含子串的字符串，所以中间是可以允许有非子串字符的，当遇见非子串字符而count又没到子串长度时，可以继续走。当count达到子串长度，说明之前遍历的这些有符合条件的串，用一个pre指针帮忙找，pre指针帮忙找第一个在HashMap中存过的，并且找到后给计数加1后的总计数是大于0的，判断是否为全局最小长度，如果是，更新返回字符串res，更新最小长度，如果不是，继续找。

class Solution {
    public String minWindow(String S, String T) {
        if(S == null || S.length() == 0)  
        return "";  
    HashMap<Character, Integer> map = new HashMap<Character, Integer>();  
    for(int i=0; i<T.length();i++)  
    {  
        if(map.containsKey(T.charAt(i)))  
        {  
            map.put(T.charAt(i),map.get(T.charAt(i))+1);  
        }  
        else  
        {  
            map.put(T.charAt(i),1);  
        }  
    }  
    int left = 0;  
    int count = 0;  
    int minLen = S.length()+1;  
    int minStart = 0;  
    for(int right=0; right<S.length();right++)  
    {  
        if(map.containsKey(S.charAt(right)))  
        {  
            map.put(S.charAt(right),map.get(S.charAt(right))-1);  
            if(map.get(S.charAt(right))>=0)  
            {  
                count++;  
            }  
            while(count == T.length())  
            {  
                if(right-left+1<minLen)  
                {  
                    minLen = right-left+1;  
                    minStart = left;                      
                }  
                if(map.containsKey(S.charAt(left)))  
                {  
                    map.put(S.charAt(left), map.get(S.charAt(left))+1);  
                    if(map.get(S.charAt(left))>0)  
                    {  
                        count--;  
                    }  
                }  
                left++;  
            }  
        }  
    }  
    if(minLen>S.length())  
    {  
        return "";  
    }  
    return S.substring(minStart,minStart+minLen); 
    }
}

solution 2:双指针

2.第一个只出现一次的字符
solution：需要一个数据容器来存放每个字符的出现次数。在这个数据容器中可以根据字符来查找它出现的次数，也就是说这个容器的作用是把每一个字符映射成一个数字。可以采用哈希表。第一次扫描时，在哈希表中出现更新一个字符出现的次数是O(n)，如果字符串长度是n，那么第一次扫描的时间复杂度是O(n)。第二次扫描时，同样O(1)能读出一个字符出现的次数。

public Character firstNotRepeating(String str){  
        if(str == null)  
            return null;  
        char[] strChar = str.toCharArray();  
        LinkedHashMap<Character,Integer> hash = new LinkedHashMap<Character,Integer>();  
        for(char item:strChar){  
            if(hash.containsKey(item))  
                hash.put(item, hash.get(item)+1);  
            else  
                hash.put(item, 1);  
        }  
        for(char key:hash.keySet())  
        {  
            if(hash.get(key)== 1)  
                return key;  
        }  
        return null;  
    }  

LeetCode版解法
[First Unique Character in a String]https://leetcode.com/problems/first-unique-character-in-a-string/description/

public int firstUniqChar(String s) {
        Map<Character, Integer> map = new LinkedHashMap<>();
        Set<Character> set = new HashSet<>();
        for (int i = 0; i < s.length(); i++) {
            if (set.contains(s.charAt(i))) {
                if (map.get(s.charAt(i)) != null) {
                    map.remove(s.charAt(i));
                }
            } else {
                map.put(s.charAt(i), i);
                set.add(s.charAt(i));
            }
        }
        return map.size() == 0 ? -1 : map.entrySet().iterator().next().getValue();
    }

3.字符串的排列
solution：求整个字符串的排列，可以看成两步，首先求所有可能出现在第一个位置的字符，即把第一个字符和后面所有的字符交换。第二步固定第一个字符，求后面所有字符的排列。这个时候仍然把后面的字符分成两部分：后面字符的第一个字符，以及这个字符之后的所有字符。然后把第一个字符逐一和它后面的字符交换。

class Solution {
    public List<List<Integer>> permute(int[] nums) {
        
        List<List<Integer>> result = new ArrayList<Integer>();
        int len = nums.length;
        if (len == 0||nums == null)  return res;
        // 采用前后元素交换的办法，dfs解题
        exchange(nums, 0, len);
        return result;
    }
    
    public void exchange(int[] nums, int i, int len) {
        // 将当前数组加到结果集中
        if(i == len-1) {
            List<Integer> list = new ArrayList<>();
            for (int j=0; j<len; j++){
                list.add(nums[j]);
            }
            res.add(list);
            return ;
        }
        // 将当前位置的数跟后面的数交换，并搜索解
        for (int j=i; j<len; j++) {
            swap(nums, i, j);
            exchange(nums, i+1, len);
            swap(nums, i, j);
        }
    }
    
    public void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}

# 递归方式
class Solution {
    public List<List<Integer>> permute(int[] nums) {
    List<List<Integer>> list = new ArrayList<>();
    // Arrays.sort(nums); // not necessary
    backtrack(list, new ArrayList<>(), nums);
    return list;
    }

    private void backtrack(List<List<Integer>> list, List<Integer> tempList, int [] nums){
    
        if(tempList.size() == nums.length){
        
            list.add(new ArrayList<>(tempList));
        } else {
            for(int i = 0; i < nums.length; i++){ 
                if(tempList.contains(nums[i])) continue; // element already exists, skip
                tempList.add(nums[i]);
                backtrack(list, tempList, nums);
                tempList.remove(tempList.size() - 1);
            }
        }   
    } 
}