LeetCode-387. First Unique Character in a String
難度: easy
Given a string
s, find the first non-repeating character in it and return its index. If it does not exist, return-1.
給一個字串s
找到第一個沒有重複的字並回傳他的index，如果沒有則回傳 -1。
(鳥翻譯請見諒，如有錯誤請協助指出，感謝
Example 1:
Input: s = "leetcode" Output: 0
Example 2:
Input: s = "loveleetcode" Output: 2
Example 3:
Input: s = "aabb" Output: -1
Constraints:
1 <= s.length <= 105sconsists of only lowercase English letters.
解題流程
- 先看懂題目想描述甚麼情境
- 開始想像程式運作該經過哪些流程
- 將經過的流程所需的判斷跟細節列出
- 實作列出的流程
先看懂題目想描述甚麼情境
應該是找出第一個不重複的字，首先想到是邊遍歷字串，邊記錄目前出現幾次，最後再重新找第一個不重複的字。
開始想像程式運作該經過哪些流程
想像中應該需要一個Map來記錄目前找到的字串總共出現幾次，遍歷字串 s 時，遇到沒有在Map裡面的字，放入Map裡面，遇到已經在Map裡面的字則直接更新出現次數，只有遍歷到底的時候，才可以確定字串 s 中不重複的第一個字是哪一個。
想像如果在邊遍歷字串 s 時，設定一個變數為字串s 的index 0 開始確認不重複的第一個字，如果目前找的字已經出現在Map，則更新變數為下一個index，等到遍歷完字串 s 後，也可以找出字串 s 中不重複的第一個字。
將經過的流程所需的判斷跟細節列出
設定一個Map紀錄出現單字，和該單字出現次數。
遍歷字串s
如果有出現在Map
Map當中單字出現次數+1
如果沒有出現在Map
Map當中加上單字，單字出現次數+1
跑完遍歷字串s後，Map上面已經紀錄所有單字跟出現次數了。
設定一個變數紀錄第一個出現的不重複單字位置，重新遍歷一次字串s，如果今天出現在Map中的次數為1則return目前遍歷到的index，沒有的話則繼續遍歷。
如果走到最後都沒有return 則回傳 -1
實作列出的流程
typescript
function firstUniqChar(s: string): number {
// trying to loop once to record appear times and record the firstIndex
/**
set 1 Map
*/
const charMap = {};
let firstAppear = 0;
for(let i=0; i < s.length; i++) {
const char = s[i];
if(!charMap[char]) {
charMap[char] = 0;
}
charMap[char]++
}
while(charMap[s[firstAppear]]) {
if(charMap[s[firstAppear]] === 1) {
return firstAppear;
}
firstAppear++
}
return -1;
};補充討論
實作的時候發現
如果再記錄完個單字出現次數後，重新檢查Map值是否有單個單字時，單純跑判斷如果有出現超過1次的單字，紀錄單個單字的index增加，最後要return的時候再判斷目前單個單字的index是否已經超出字串s ，這會跑得比上面的寫法快一點點。(以下方程式範例測試)
比較快的原因，有可能是因為while條件設定不同，這邊設定只有Map單字出現次數大於1的時候才要去增加單個單字的index，但上面的寫法會跑進每個Map裡有的單字。(有待確認)
function firstUniqChar(s: string): number {
// trying to loop once to record appear times and record the firstIndex
/**
set 1 Map
*/
const charMap = {};
let firstAppear = 0;
for(let i=0; i < s.length; i++) {
const char = s[i];
if(!charMap[char]) {
charMap[char] = 0;
}
charMap[char]++
}
while(charMap[s[firstAppear]]>1) {
firstAppear++
}
return charMap[s[firstAppear]] ? firstAppear : -1;
};另外有發現leetcode上大神的超神寫法Java 7 lines solution 29ms – First Unique Character in a String – LeetCode
這邊用typescript模擬一下大大的程式碼，大概流程是(範例為下方程式碼):
- 先創建一個陣列charCount，長度為26，每個index內容都為0(因為要用陣列的index來做為各單字，charCount[index]表示該單字出現的次數初始為0)
- 遍歷字串s ，來將有出現單字的位置+1(代表這個單字多出現一次了)
- 遍歷完字串後，會取得所有單字的出現次數
- 再重新遍歷一次字串s，這次有遇到值為1的就可以return了
大神能想到用charCode的位置來做map紀錄，真的很厲害，雖然看到題目大部分的人可能一開始就想到Map，但可以利用charCode位置來做紀錄，可以知道大神創意的背後是對charCode的機制有一定的理解。
function firstUniqChar(s: string): number {
const MAX_CHAR = 26;
const charCount = new Array(MAX_CHAR).fill(0);
for (let i = 0; i < s.length; i++) {
const char = s[i];
const appearPos = char.charCodeAt(0) - "a".charCodeAt(0);
charCount[appearPos]++
}
for (let i = 0; i < s.length; i++) {
const char = s[i];
const appearPos = char.charCodeAt(0) - "a".charCodeAt(0);
if(charCount[appearPos] === 1) {
return i
}
}
return -1;
};感謝閱讀，如果有錯誤或是講得不清楚的部分，再請留言指教