字符串经典问题

1. 验证回文串

验证回文串
如果在将所有大写字符转换为小写字符、并移除所有非字母数字字符之后，短语正着读和反着读都一样。则可以认为该短语是一个 回文串 。

字母和数字都属于字母数字字符。

给你一个字符串 s，如果它是 回文串 ，返回 true ；否则，返回 false 。

示例 1：

输入: s = “A man, a plan, a canal: Panama”
输出：true
解释：“amanaplanacanalpanama” 是回文串。

1.1 先转换为都是小写的字符串，然后比较是否是回文串

首先根据题目的条件，先使用StringBuilder来存储小写字符串，如果s里面不是小写那么就跳过，可以使用Character.isLetterOrDigit()判断是否为字符，然后使用toLowerCase转换成小写，然后就都是小写的字符串，进行字符串回文比较。

    public boolean isPalindrome(String s) {StringBuilder sb = new StringBuilder();for(int i=0;i<s.length();i++){char c =s.charAt(i);if(Character.isLetterOrDigit(c)){sb.append(Character.toLowerCase(c));}}String str = sb.toString();int left =0;int right = str.length()-1;while(left<right){if(str.charAt(left) != str.charAt(right)){return false;}left++;right--;}return true;}

总的时间复杂度时O(n),空间复杂度O(n)

不过这里我还有个想法，就是一次循环，碰到，空格就跳过，然后将字符转为小写使用双指针进行比较，这样就可以使用一次遍历。

1.2 一次循环

  public boolean isPalindrome(String s) {int n =s.length();int left =0;int right = n-1;while(left<right){while(left<right && !Character.isLetterOrDigit(s.charAt(left))){++left;}while(left<right && !Character.isLetterOrDigit(s.charAt(right))){--right;}if(left<right){if(Character.toLowerCase(s.charAt(left) ) != Character.toLowerCase(s.charAt(right))){return false;}++left;--right;}}return true;}

这一题如果知道了isLetterOrDigit，就比较简单了，不需要使用额外的判断。

2. 字符串中的第一个唯一字符

字符串中的第一个唯一字符
给定一个字符串 s ，找到 它的第一个不重复的字符，并返回它的索引 。如果不存在，则返回 -1 。
示例 1：

输入: s = “leetcode”
输出: 0
示例 2:

输入: s = “loveleetcode”
输出: 2
示例 3:

输入: s = “aabb”
输出: -1

2.1 HashMap

统计每个字符出现的次数，使用hashmap比较合适，然后遍历字符串找到对应的map里面值为1的结果，就是不重复的字符。

    public int firstUniqChar(String s) {HashMap<Character,Integer> map = new HashMap<>();for(int i=0;i<s.length();i++){map.put(s.charAt(i),map.getOrDefault(s.charAt(i),0)+1);}for(int i=0;i<s.length();i++){if(map.get(s.charAt(i))==1){return i;}}return -1;}

3. 有效的字母异位词

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

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

3.1 字符数组排序

刚看到这个方法的时候还是有点没想到，因为将字符经过排序后都是按照一定顺序排列的，只需要将两个字符串排序后的结果比较就可以了。

    public boolean isAnagram(String s, String t) {char [] ch1 = s.toCharArray();char [] ch2 = t.toCharArray();Arrays.sort(ch1);Arrays.sort(ch2);return new String(ch1).equals(new String(ch2));}

3.2 哈希表

题目提示了统计字符出现的次数，很显然使用哈希表。

    public boolean isAnagram(String s, String t) {if(s.length()!=t.length()) return false;char [] ch1 = s.toCharArray();Map<Character,Integer> map1 = getMapStr(s);Map<Character,Integer> map2 = getMapStr(t);for(char ch: ch1){if(!map2.containsKey(ch) || map1.get(ch) != map2.get(ch)){return false;}}return true;}private Map<Character,Integer> getMapStr(String str){char [] chars = str.toCharArray();Map<Character,Integer> map = new HashMap<>();for(char ch:chars){map.put(ch,map.getOrDefault(ch,0)+1);}return map;}

但是这个方法在力扣里面测试有个数据跑不通。

3.3 哈希映射

首先先设置一个26位长的数组，然后这个数组里面下标就对应着字符串里面的下标，然后每次遍历的时候都要将同一个位置的元素如果s里面存在那么数组对应元素的个数就自增，t里面也对应这个元素就自减，如果最后每位上的元素值都是0，就意味着是一样的。

    public boolean isAnagram(String s, String t) {if(s.length()!=t.length()) return false;int  [] res = new int [26];for(int i=0;i<s.length();i++){res[s.charAt(i) - 'a']++;res[t.charAt(i) - 'a']--;}for(int i=0;i<26;i++){if(res[i]!=0){return false;}}return true;
}