清风的技术小屋

不为所动, 做更专业的自己

0%

LeetCode 387 - First Unique Character in a String

问题描述

Given a string, find the first non-repeating character in it and return it's index. If it doesn't exist, return -1.

Examples:

1
2
3
4
5
s = "leetcode"
return 0.

s = "loveleetcode",
return 2.

Note: You may assume the string contain only lowercase letters.

Related Topics: Hash Table, String

原问题: 387. First Unique Character in a String

中文翻译版: 387. 字符串中的第一个唯一字符

解决方案

本题需要找到第一个不重复出现的字符的位置,因此在遍历字符串时需要保存字符的位置。由于字符串中只有小写字母,因此可以创建一个大小为 26 的数组,存储 26 个字母在字符串中出现位置,由于还需要判断该字母是否重复出现,这时可以用一个特殊值表示该字母在字符串中重复出现。数组元素的值分三种情况:

  • -1 表示该字母已经重复出现
  • 0 表示该字母未在字符串中出现
  • 正整数表示该字母第一次在字符串中出现的位置 (位置从 1 开始)

根据输入的字符串构造出这个数组后,我们可以很快找到第一个不重复出现的字符的位置 (即数组元素中值最小的那个,不包括 -1 和 0)。实现代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
#include <iostream>
#include <string>
#include <cstring>
using namespace std;

class Solution {
public:
int firstUniqChar(string s)
{
if (s.size() == 0)
return -1;
else if (s.size() == 1)
return 0;

/* letters[i]
* -1 means letter repeat
* 0 means letter not appear
* > 0 means position of letter in string (index starts from 1)
*/
int letters[26];
int pos;

memset(letters, 0, sizeof(letters));
for (int i=0; i<s.size(); i++) {
pos = s[i] - 'a';
if (letters[pos] > 0)
letters[pos] = -1;
else if (letters[pos] == 0)
letters[pos] = i + 1;
}

int ret = -1;
for (int i=0; i<26; i++) {
if (letters[i] > 0) {
if (ret == -1)
ret = letters[i] - 1;
else if (ret > letters[i] - 1)
ret = letters[i] - 1;
}
}

return ret;
}
};

int main()
{
Solution solu;

string str1 = "aadadaad";
cout << str1 << ": " << solu.firstUniqChar(str1) << endl;

string str2 = "loveleetcode";
cout << str2 << ": " << solu.firstUniqChar(str2) << endl;

return 0;
}