这次题目有三题，分别是字符串中的第一个唯一字符、赎金信和有效的字母异位词.
今天三道题目的思路都差不多，感觉都是两个数组的交集 II的变形,内容篇幅可能比较长，目录可以快速定位到对应题目的解题思路&题解.

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

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

示例：

1
2
3
4
5
s = "leetcode"
返回 0

s = "loveleetcode"
返回 2

解题思路&题解

拿到题目的第一反应是和之前两个数组的交集 II一样的思路。
通过哈希表记录元素出现的下标，然后扫码字符串找出出现的次数为1的元素，然后返回该元素的下标。
大致思路:

  1. 数组0-25表示’a’ -> ‘z’
  2. 哈希表使用一个26长度的数组表示
  3. 数组内容表示元素出现次数

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
func firstUniqChar(s string) int {
	items := [26]int{}
	for i := 0; i < len(s); i++ {
		items[s[i]-'a']++
	}
	for i := 0; i < len(s); i++ {
		if items[s[i]-'a'] == 1 {
			return i
		}
	}
	return -1
}

赎金信

给定一个赎金信 (ransom) 字符串和一个杂志(magazine)字符串，判断第一个字符串 ransom 能不能由第二个字符串 magazines 里面的字符构成。如果可以构成，返回 true ；否则返回 false。

(题目说明：为了不暴露赎金信字迹，要从杂志上搜索各个需要的字母，组成单词来表达意思。杂志字符串中的每个字符只能在赎金信字符串中使用一次。)

示例 1：

1
2
输入：ransomNote = "a", magazine = "b"
输出：false

示例 2：

1
2
输入：ransomNote = "aa", magazine = "ab"
输出：false

示例 3：

1
2
输入：ransomNote = "aa", magazine = "aab"
输出：true

解题思路&题解

这题与上一题差不多，思路上甚至更像两个数组的交集 II，也是通过一个数组哈希表存储字符出现的次数。
第二次遍历的时候将数组内容减一，当内容为0时表示内容不够则返回false

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
func canConstruct(ransomNote string, magazine string) bool {
	conMap := [26]int{}
	for i := 0; i < len(magazine); i++ {
		conMap[magazine[i]-'a']++
	}
	for i := 0; i < len(ransomNote); i++ {
		if conMap[ransomNote[i]-'a'] == 0 {
			return false
		}
		conMap[ransomNote[i]-'a']--
	}
	return true
}

有效的字母异位词

给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的字母异位词。
注意：若 s 和 t 中每个字符出现的次数都相同，则称 s 和 t 互为字母异位词。

示例 1:

1
2
输入: s = "anagram", t = "nagaram"
输出: true

示例 2:

1
2
输入: s = "rat", t = "car"
输出: false

解题思路&题解

这题应该就是两个数组的交集 II的变形了，今天这三题整体上思路都没啥区别，不过多赘述了。

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
func isAnagram(s string, t string) bool {
	res := [26]int{}
	for i := 0; i < len(s); i++ {
		res[s[i]-'a']++
	}
	for i := 0; i < len(t); i++ {
		if res[t[i]-'a'] == 0 {
			return false
		}
		res[t[i]-'a']--
	}
	for _, v := range res {
		if v != 0 {
			return false
		}
	}
	return true
}