【LeetCode】387. First unique character in string

The more you do the questions, the more you feel like a vegetable chicken

🧸 Reading questions

Find the first , The character that appears once , The subscript .

🧸 Code O(N)

Ideas ： Find by mapping , Open an array to record the number of times each caption appears , Then find out that the first one in the array is 1 Mapped characters for ！

class Solution {
    
public:
    int firstUniqChar(string s) {
    
        int countArr[26] = {
     0 };
        // Count the times 
        for (int i = 0; i < s.size(); ++i)
        {
    
            countArr[s[i] - 'a']++;
        }
        for (int j = 0; j < s.size();++j)
        {
    
            if (countArr[s[j] - 'a'] == 1)
            {
    
                return j;
            }
        }
        return -1;
    }
};

🧸 Decoding code

Solve the problem by mapping
int countArr[26] = { 0 };

The title says there are only lowercase letters , So the mapped array is opened directly 26 Just one ！
And initialized to 0;
take s Each character in maps to ,countArr The subscript ,countArr The number stored in the subscript is The number of times this character appears ！

for (int i = 0; i < s.size(); ++i)
{
  countArr[s[i] - 'a']++;
}

i yes countArr Index of the array , The scope is s.size()
For example, find l , hypothesis s[i] What's stored is l , Traversal character array
use 'l' - 'a' be equal to 11, That is to say l Mapping to countArr The subscript
So in countArr[11] Location ++ , If l Appear twice in countArr[11] The position of ++

for (int j = 0; j < s.size();++j)
{
  if (countArr[s[j] - 'a'] == 1)
  {
    return j;
  }
}

This loop is traversal s character string
j yes s The subscript of a string , The scope is s.size()
For example, find l, hypothesis l The position is s[j]
because 'l' - 'a' be equal to 11, That is to say l Mapping to countArr[] The subscript , This subscript stores l Number of occurrences ！
So if countArr[s[j] - 'a'] == 1
that s[j] Medium j Namely , Only once l character , The subscript ！

🧸 I'm almost writing circles , I hope you understand ！！！

🧸 The solution of other big guys

The solution is O(N²)
Traversal array , Look in the middle at both ends , If both are found and the subscripts are the same , Then this character is in the whole s Only once in a while , In this case, you can directly return the subscript

class Solution {
    
public:
    int firstUniqChar(string s) {
    
        for(int i = 0;i<s.size();++i)
		{
    
			if(s.find(s[i]) == s.rfind(s[i]))
			{
    
				return i;
			}
		}
        return -1;
    }
};

come on. , I wish you get what you want offer！