Leetcode Exercise 5

Wendy Wu

Published in

W-Learning Note

7 min readFeb 7, 2019

Unique Email Addresses

Loading...

Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepar

leetcode.com

Description

Every email consists of a local name and a domain name, separated by the @ sign.
For example, in alice@leetcode.com, 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, "alice.z@leetcode.com" and "alicez@leetcode.com"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 m.y+name@email.com will be forwarded to my@email.com. (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?

看起來有點長，大意是說email是由local name和domain name組成，中間是由@來區隔，例如alice@leetcode.com，alice 是local name，leetcode.com 則是domain name。

除此之外，email是可以包含'.'或是'+'。

如果在local name加入'.' ，mail會傳送到沒有'.' 的地址，例如"alice.z@leetcode.com" 和"alicez@leetcode.com" 是傳送到相同的地址。(這項規則不適用於domain name)

如果在local name加入'+' ，任何在第一個加號之後的內容會被忽略，例如m.y+name@email.com 會被傳送到my@email.com。(同樣地，這項規則不適用於domain name)

這兩個規則是能同時使用的。

當題目給了一組email的清單時，要回傳實際上有幾個不同地址的email。

Example

#1
Input:
["test.email+alex@leetcode.com","test.e.mail+bob.cathy@leetcode.com","testemail+david@lee.tcode.com"]Output: 2Explanation: 
"testemail@leetcode.com" and "testemail@lee.tcode.com" actually receive mails

構思

先個別處理每一個email，按照規則簡化
每個email先拆分local name和domain name，只針對local name的部分處理，先處理'+'，去掉後面的內容，再將所有'.' 刪除
全部處理完後再去除掉重複的地址
計算總數

實作程式碼

# @param {String[]} emails
# @return {Integer}
def num_unique_emails(emails)
  emails = emails.map do |email|
    email = email.split("@")
    local = email[0].split("+")
    local = local[0].delete(".")
    email = local + "@" + email[1]
  end
  emails.uniq.size     
end

split:

會將string按照設定的條件，拆換成array，在這邊的用法就是用”@”將email address分成兩邊：

uniq:

回傳一個去掉重複值的Array

結果

beats 94.29%

Runtime最短的寫法: 60ms

def num_unique_emails(emails)     
  uniques = 0     
  ht = Hash.new(0)     
  emails.each do |e|         
    at_position = e.index('@')                  
   
    if e.include? '+'             
      local = e[0,e.index('+')]         
    else             
      local = e[0,at_position]         
    end                      domain = e[at_position..-1]         
    local.gsub!('.','')                      canonical = local << domain                  
    uniques+=1 if ht[canonical]==0          
    ht[canonical]+=1     
  end    
  uniques 
end

一樣是對每個email個別處理，先用index找出'@'的位置，再判斷是否有'+'，有的話local就是開頭到'+'的位置，沒有的話local就是開頭到'@'之前的位置，再將local的'.'用gsub!代換成空的，而domain則是從'@'到結尾。

最後將local和domain合在一起變成完整的email地址存入canonical這個變數，這時判斷ht這個hash中key為canonical時，value是否等於0(因為初始化hash的時候給了default value 0，所以若canonical為空時會回傳0)，等於0的話會將uniques的值加1，並且在ht中在key等於canonical的value加上1，這樣下次遇到一樣的canonical時，uniques的值便不會改變，最後再回傳uniques即是答案。

index:

回傳在字串中第一個遇見給定的子字串或字串樣板(Regexp)的索引