string类问题总结

1. Unique Characters of a String 字符串中不同的字符

Implement an algorithm to determine if a string has all unique characters. What if you cannot use additional data structure?

思路分析：这道题让我们判断一个字符串中是否有重复的字符，要求不用特殊的数据结构，这里应该是指哈希表之类的不让用。像普通的整型数组应该还是能用的，这道题的小技巧就是用整型数组来代替哈希表，在之前Bitwise AND of Numbers Range 数字范围位相与的解法二中也用到过这种方法。由于ASCII表里的基本表共有128个字符，也就是可以用键盘表示出来的，整个表共有256个字符，所以我们只要用一个大小为256的整型数组就可以包含所有的字符，我们遍历输入字符串，对每一个字符都存入到相应位置，并赋值1，如果遇到已经为1的，说明之前出现过该字符，返回false，如果遍历完s，则返回true，代码如下:

我把i的值做了+1处理，防止aab这样的特例出现

public class Solution {
    /**
     * @param str: a string
     * @return: a boolean
     */
    public boolean isUnique(String str) {
        if (str == null) {
            return false;
        }
        int chars[] = new int[256];
        int size = str.length();
        for (int i = 0; i < size; i++) {
            char current = str.charAt(i);
            if (chars[(int)current] != 0) {
                return false;
            }
            chars[(int)current] = i + 1;//aab的反例
        }
        return true;
    }
}

2.上面题的马甲变形-----isPermutation

判断是不是permutation其实就是判断两个字符串中各个字母的数量是否相等！！！

复杂度为0(n)

private static boolean isPer(String A, String B) {
        if (A == null && B == null) {
            return true;
        }
        if (A == null || B == null) {
            return false;
        }
        int size1 = A.length();
        int size2 = B.length();
        if (size1 != size2) {
            return false;
        }
        
        int count[] = new int[256];
        for (int i = 0; i < size1; i++) {
            char current = A.charAt(i);
            count[(int)current]++;
            current = B.charAt(i);
            count[(int)current]--;
        }
        
        for (int i = 0; i < 256; i++) {
            if (count[i] != 0) {
                return false;
            }
        }
        return true;
    }

如果不考虑复杂度，可以讲两个stringsort一遍，然后进行逐个char的比对

--------------------------分割线---------------------------------

Palindromes相关题目

Count Palindromes

Count the number of possible palindrome substrings in a string. A palindrome is a word that reads the same way spelled backwards.
Example:
input: lasagna.
Possible palindromes are asa, l,a,s,a,g,n,a.
output: count is 8.

input:hellolle
ellolle,lloll,lol,ll,ll,h,e,l,l,o,l,l,e.
output:13.

枚举palindromes的起始位置，机智！

public static int countPalindromes(String a) {
        int globalCount = a.length();
        for (int mid = 1; mid < a.length() - 1; mid++) {
            int count = 0;

            int low = mid - 1;
            int high = mid + 1;
            while (low >= 0 && high < a.length() && a.charAt(low--) == a.charAt(high++))
                count++;

            globalCount += count;
            count = 0;

            low = mid - 1;
            high = mid;
            while (low >= 0 && high < a.length() && a.charAt(low--) == a.charAt(high++))
                count++;

            globalCount += count;
        }

        return globalCount;
    }

--------------------------分割线---------------------------------

3. Group Anagrams

Given an array of strings, group anagrams together.

For example, given: ["eat", "tea", "tan", "ate", "nat", "bat"], 
Return:

[
  ["ate", "eat","tea"],
  ["nat","tan"],
  ["bat"]
]

 

排序哈希表法

复杂度

时间 O(NKlogK) 空间 O(N)

思路

判断两个词是否是变形词，最简单的方法是将两个词按字母排序，看结果是否相同。这题中我们要将所有同为一个变形词词根的词归到一起，最快的方法则是用哈希表。所以这题就是结合哈希表和排序。我们将每个词排序后，根据这个键值，找到哈希表中相应的列表，并添加进去。为了满足题目字母顺序的要求，我们输出之前还要将每个列表按照内部的词排序一下。可以直接用Java的Collections.sort()这个API。

注意

将字符串排序的技巧是先将其转换成一个char数组，对数组排序后再转回字符串

public class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        Map<String, List<String>> map = new HashMap<String, List<String>>();
        for(String str : strs){
            // 将单词按字母排序
            char[] carr = str.toCharArray();
            Arrays.sort(carr);
            String key = new String(carr);
            List<String> list = map.get(key);
            if(list == null){
                list = new ArrayList<String>();
            }
            list.add(str);
            map.put(key, list);
        }
        List<List<String>> res = new ArrayList<List<String>>();
        // 将列表按单词排序
        for(String key : map.keySet()){
            List<String> curr = map.get(key);
            Collections.sort(curr);
            res.add(curr);
        }
        return res;
    }
}

 ------------------分割线------------

滑动窗口类问题：1. Longest Substring Without Repeating Characters 2. 

　　　　　　　　2. Minimum Window Substring

　　　　　　　　3.Substring with Concatenation of All Words