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:

s = "leetcode"
return 0.

s = "loveleetcode",
return 2.

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

解题思路 1

利用两个 hashtable，就能完成统计字符出现次数和出现的位置。

class Solution {
public:
	int firstUniqChar(string s) {
		unordered_map<char, unsigned int> crmap;
		unordered_map<char, unsigned int> cimap;

		for (size_t i = 0; i < s.size(); i++) {
			crmap[s[i]]++;
			cimap[s[i]] = i;
		}

		char c = NULL;
		string::iterator it = s.begin();
		while (it != s.end()) {
			if (crmap[*it] == 1) {
				c = *it;
				break;
			}
			it++;
		}

		return (c == NULL) ? -1 : cimap[c];
	}
};

解题思路 2

利用 hashtable 的变形

unordered_map<char, vector<size_t>>

key 表示字符，value 是 key 出现的位置的集合