首页 > 代码库 > string类问题总结
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这样的特例出现
1 public class Solution { 2 /** 3 * @param str: a string 4 * @return: a boolean 5 */ 6 public boolean isUnique(String str) { 7 if (str == null) { 8 return false; 9 }10 int chars[] = new int[256];11 int size = str.length();12 for (int i = 0; i < size; i++) {13 char current = str.charAt(i);14 if (chars[(int)current] != 0) {15 return false;16 }17 chars[(int)current] = i + 1;//aab的反例18 }19 return true;20 }21 }
2.上面题的马甲变形-----isPermutation
判断是不是permutation其实就是判断两个字符串中各个字母的数量是否相等！！！
复杂度为0(n)
1 private static boolean isPer(String A, String B) { 2 if (A == null && B == null) { 3 return true; 4 } 5 if (A == null || B == null) { 6 return false; 7 } 8 int size1 = A.length(); 9 int size2 = B.length();10 if (size1 != size2) {11 return false;12 }13 14 int count[] = new int[256];15 for (int i = 0; i < size1; i++) {16 char current = A.charAt(i);17 count[(int)current]++;18 current = B.charAt(i);19 count[(int)current]--;20 }21 22 for (int i = 0; i < 256; i++) {23 if (count[i] != 0) {24 return false;25 }26 }27 return true;28 }
如果不考虑复杂度，可以讲两个stringsort一遍，然后进行逐个char的比对
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数组，对数组排序后再转回字符串
1 public class Solution { 2 public List<List<String>> groupAnagrams(String[] strs) { 3 Map<String, List<String>> map = new HashMap<String, List<String>>(); 4 for(String str : strs){ 5 // 将单词按字母排序 6 char[] carr = str.toCharArray(); 7 Arrays.sort(carr); 8 String key = new String(carr); 9 List<String> list = map.get(key);10 if(list == null){11 list = new ArrayList<String>();12 }13 list.add(str);14 map.put(key, list);15 }16 List<List<String>> res = new ArrayList<List<String>>();17 // 将列表按单词排序18 for(String key : map.keySet()){19 List<String> curr = map.get(key);20 Collections.sort(curr);21 res.add(curr);22 }23 return res;24 }25 }
string类问题总结