第一题 字符串中的第一个惟一字符

题目信息

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

 

示例：

s = “leetcode”
返回 0

s = “loveleetcode”
返回 2
 

提醒：你能够假设该字符串只蕴含小写字母。

解题思路

对于这道题，最暴力的办法天然是：

对于字符串的每个字符，都查找一遍字符串，若找到雷同的字符，则开始查找下一个字符；若找不到雷同的字符，则返回该字符的索引。

暴力解法简略易懂的同时，也进行了大量的无意义操作，若惟一字符位于字符串尾部，则该算法的计算量将异样宏大。算法的工夫复杂度为O（n^2）

对此，咱们思考引入新的数据结构辅助实现对字符串的查问，即哈希表

哈希表是一种奇妙并且实用的数据结构。它是一个无序的key/value对的汇合，其中所有的key都是不同的，而后通过给定的key能够在常数工夫复杂度内检索、更新或删除对应的value。
援用
在Go语言中，一个map就是一个哈希表的援用，map类型能够写为map[K]V，其中K和V别离对应key和value。map中所有的key都有雷同的类型，所有的value也有着雷同的类型，然而key和value之间能够是不同的数据类型。其中K对应的key必须是反对==比拟运算符的数据类型，所以map能够通过测试key是否相等来判断是否曾经存在。


详见
https://haicoder.net/golang/g…

代码

func firstUniqChar(s string) int {
    m:= make(map[rune]int, 26)
    for _, ch := range s {
        m[ch]++
    }
    for i, ch := range s {
        if m[ch] == 1 {
            return i
        }
    }
    return -1
}

复杂度剖析

工夫复杂度：O(n)，其中 n 是字符串 s 的长度。咱们须要进行两次遍历。

空间复杂度：O(∣Σ∣)，其中 Σ 是字符集，在本题中 s 只蕴含小写字母，因而 ∣Σ∣≤26。咱们须要 O(∣Σ∣) 的空间存储哈希映射。

小优化

浏览官网代码

咱们能够看到，官网在应用哈希表时，将读到的字符减去字符a的码值再进行查表
通过比照尝试，发现这样能够大幅度缩小执行工夫

第二题 无效的字母异位词

题目信息

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

留神：若 s 和 t 中每个字符呈现的次数都雷同，则称 s 和 t 互为字母异位词。

 

示例 1:

输出: s = “anagram”, t = “nagaram”
输入: true
示例 2:

输出: s = “rat”, t = “car”
输入: false
 

提醒:

1 <= s.length, t.length <= 5 * 104
s 和 t 仅蕴含小写字母
 

进阶: 如果输出字符串蕴含 unicode 字符怎么办？你是否调整你的解法来应答这种状况？

相干标签
哈希表
字符串
排序

解题思路

将两个字符串各自存入哈希表记录每个字符呈现的次数，再通过查表一一获得呈现次数比照

代码

func isAnagram(s string, t string) bool {
    m1:= make(map[rune]int, 26)
    m2:= make(map[rune]int, 26)
    for _, ch := range s {
        m1[ch-'a']++
    }
    for _, ch := range t {
        m2[ch-'a']++
    }
    if len(s)<len(t){
        s=t
    }
    for _, ch := range s {
        if m1[ch-'a']!=m2[ch-'a']{
            return false
        }
    }
    return  true

}

官网解析

对于应用哈希表的办法，因为是两个字符串的比拟，在将第二个字符串记入第二个哈希表的时候能够抉择以第一个哈希表的革除代替，在节俭了空间的同时，也省去了将两个哈希表比拟的工夫

另外，官网还承受了另一种思路 排序法
将两个字符串进行排序之后再进行比照
因为复杂度较高，暂不予以阐述

复杂度剖析

工夫复杂度：O(n)，其中 n 为 s 的长度。

空间复杂度：O(S)，其中 S 为字符集大小，此处S=26。