这次题目有三题,分别是字符串中的第一个唯一字符赎金信有效的字母异位词.
今天三道题目的思路都差不多,感觉都是两个数组的交集 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 的字母异位词。
注意:若 st 中每个字符出现的次数都相同,则称 st 互为字母异位词。

示例 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
}