LeetCode算法题929解题思路

原题

929. Unique Email Addresses

Every email consists of a local name and a domain name, separated by the @ sign.

For example, in [email protected], alice is the local name, and leetcode.com is the domain name.

Besides lowercase letters, these emails may contain ‘.’s or ‘+’s.

If you add periods (‘.’) between some characters in the local name part of an email address, mail sent there will be forwarded to the same address without dots in the local name. For example, “[email protected]” and “[email protected]” forward to the same email address. (Note that this rule does not apply for domain names.)

If you add a plus (‘+’) in the local name, everything after the first plus sign will be ignored. This allows certain emails to be filtered, for example [email protected] will be forwarded to [email protected] (Again, this rule does not apply for domain names.)

It is possible to use both of these rules at the same time.

Given a list of emails, we send one email to each address in the list. How many different addresses actually receive mails?

Example 1

1
2
3
Input: ["[email protected]","[email protected]","[email protected]"]
Output: 2
Explanation: "[email protected]" and "[email protected]" actually receive mails

Note

  • 1<= emails[i].length <= 100
  • 1<= emails.length <= 100
  • Each emails[i] contains exactly one ‘@’ character.

解题思路

思路1

看完题目后首先想到用string.Split()来把每一个email地址拆分成local name 和 domain name组成的数组,然后在处理local name部分, 最后用strings.Join()把local name 和 domain name合并成完整的email地址。

思路1的实现:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
func numUniqueEmails(emails []string) int {
var uniqueEmails = map[string]bool{}
for _, email := range emails {
emailComponents := strings.Split(email, "@")
localName := emailComponents[0]
if plusIndex := strings.Index(localName, "+"); plusIndex != -1 {
localName = localName[0:plusIndex]
}
localName = strings.Replace(localName, ".", "", -1)
emailComponents[0] = localName
uniqueEmails[strings.Join(emailComponents, "@")] = true
}
return len(uniqueEmails)
}

思路1的结果:

毫无疑问,这个思路是有问题的,空间和时间都不行。

思路2

字符串本质是个数组,那么我们通过下标的方式来截取字符串,看看效率会不会高一些

思路2的实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
func numUniqueEmails(emails []string) int {
var uniqueEmails = map[string]bool{}
for _, email := range emails {
localName := email[0:strings.Index(email, "@")]
domainName := email[strings.Index(email, "@")+1:]
if plusIndex := strings.Index(localName, "+"); plusIndex > -1 {
localName = localName[0:plusIndex]
}
if dotIndex := strings.Index(localName, "."); dotIndex > -1 {
localName = strings.Replace(localName, ".", "", -1)
}
uniqueEmails[localName+"@"+domainName] = true
}
return len(uniqueEmails)
}

思路2的结果

结果好很多,但是还是不能令人满意

进一步改进

思路

观察思路2的实现,发现遗漏了一个可以优化的地方:代码里查找@字符的时候进行了两次,是多余的,所以针对这个地方优化了一下。
然后又预先申明了几个变量,避免循环里重复申明
根据题目得知emails的长度和emails里面每个元素的长度都不会超过100,所以index相关的都申明为了int8
for循环改为下标访问,避免产生更多的内存消耗

实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
func numUniqueEmailsPro(emails []string) int {
var uniqueEmails = map[string]bool{}
var indexOfAt int8
var localName string
var plusIndex int8 = -1
var dotIndex int8 = -1
for i := 0; i < len(emails); i++ {
indexOfAt = int8(strings.Index(emails[i], "@"))
localName = emails[i][0:indexOfAt]
if plusIndex = int8(strings.Index(localName, "+")); plusIndex > -1 {
localName = localName[0:plusIndex]
}
if dotIndex = int8(strings.Index(localName, ".")); dotIndex > -1 {
localName = strings.Replace(localName, ".", "", -1)
}
uniqueEmails[localName+"@"+emails[i][indexOfAt+1:]] = true
}
return len(uniqueEmails)
}

改进结果

复盘

其实最后一次改进的那几点是一次一次试出来的,但是并不是每一个都有效果,时间上的进步是明显的,但是空间上的就不好评估了,因为空间上在尝试第一次优化的时候就已经只消耗了5.6M,后面就没有变化,只有轻微的排名百分比的变化。

加载评论框需要科学上网