IT僧

解題12. 從字串中尋找第一個不重複的字母 (只用一層 loop)

27 12 月, 2021 欣迪

出處： https://leetcode.com/explore/interview/card/top-interview-questions-easy/127/strings/881/

Given a string s, find the first non-repeating character in it and return its index. If it does not exist, return -1.

Ex1
Input: s = "leetcode"
Output: 0

Ex2
Input: s = "loveleetcode"
Output: 2

Ex3
Input: s = "aabb"
Output: -1

Constraints:

• 1 <= s.length <= 105
• s consists of only lowercase English letters.

var firstUniqChar = function(s) {
    let i = 0
    const used = new Set()
    for(let i = 0; i < s.length; i++ ) {      
        if(!used.has(s[i])) {
            used.add(s[i])
            const idx = s.indexOf(s[i], i+1)
            if( idx === -1) return i
        }
    }
    return -1
}

技巧

其實這題本身難度不高，但是一般人通常會使用 2 個 loop 去解決。 但是如果善用 indexOf 這個內建 function，可以用一個 loop 去完成。

首先，為了避免偵測重複的字元，用一個 new Set() 去紀錄已經檢查過的文字。

沒檢查過的文字用 indexOf 這個功能。這邊特別的小技巧就是， indexOf 的第二個參數是起始位置，跳過已經檢索過的位置，從下一個字元開始檢查。這樣的做法可以省去不必要的檢查，減少時間和資源的消耗。

訂閱 IT-Monk

訂閱最新文章的發布消息! 😚😚😚

姓名

Email*