Title: Daily practice (23) : The first character that appears only once

Categories: [sword refers to offer]

Tags: Daily Practice

date: 2022/02/22

Daily practice (23) : The first character that appears only once

Find the first character in the string s that occurs only once. If not, a single space is returned. The s contains only lowercase letters.

Example 1:

Enter: s = “abaccdeff”

Output: ‘b’

Example 2:

Enter: s = “”

Output:”

Limitations:

0 <= the length of s <= 50000

Source: LeetCode

Link: leetcode-cn.com/problems/di…

Method 1: hash table

Train of thought

1. The string is traversed twice.

  • Traversal strings, use the hash table to check whether the number of characters is greater than 1.
  • Iterate over the string agains, finds the first “character of quantity 1” in the hash table, and returns.

algorithm

1. Character statistics: iterate over each character C in string S;

  • If dic does not contain the key c:, add the key-value pair (c, True) to DIC, representing the number of character C is 1.

  • If dic contains key C:, change the key-value pair of key C to (c, False), indicating that the number of character C is greater than 1.

2. Search for 1 character: iterate over each character c in string S;

  • If the dic key c is True:, c is returned.

3. Return ‘ ‘, indicating that the string has no characters of 1.

char firstUniqChar(string s) {
    if (s.empty()) { 	// Pay attention to the processing of boundary cases! Especially if s is an empty string
        return ' ';
    }
	unordered_map<int.bool> dic;
    for (char c : s) {
        dic[c] = dic.find(c) == dic.end(a); }for (char c : s) {
        if (dic[c]) {
            returnc; }}return ' ';
}
Copy the code

Method 2: skillfully use the string container lookup function

Ideas and Algorithms

  • S.type (s[I]) : returns the first occurrence of s[I] in string s from left to right;
  • S.find (s[I]) : returns the position where s[I] first appears in string s from right to left;

While this method looks clean in code, it is time intensive!

char firstUniqChar(string s) {
    if (s.empty()) {	// Pay attention to the processing of boundary cases! Especially if s is an empty string
        return ' ';
    }
    int n = s.size(a);for(int i = 0; i < n; i++){
        if(s.find(s[i]) == s.rfind(s[i])){
            returns[i]; }}return ' ';
}

Copy the code