Problem Statement
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.
Solutions
version 1
The first idea came to my mind is using double loops to check the Repeatability of every single charator. And I also used a dynamic allocated arrary to store whether every charator is duplicated.
int firstUniqChar(char* s) {
int len = strlen(s);
if (len == 1)
return 0;
int * status = (int*)malloc(len*sizeof(int));
memset(status, 0, len*sizeof(int));
int i;
int j;
for (i = 0; i < len - 1; i++) {
bool has_repeat = false;
if (status[i] == 1)
continue;
for (j = i + 1; j < len; j++) {
if (s[i] == s[j]) {
status[j] = 1;
has_repeat =true;
}
}
if (!has_repeat) {
free(status);
return i;
}
}
free(status);
return -1;
}
It is accepted successfully, but the performance is not ideal. Because it's time complexity is . I think it has the solution definitely.
Version 2
Instead of the allocated array with the string's length, the letter table with 26 letters is enough for this scenario:
int firstUniqChar(char* s) {
int len = strlen(s);
int * alphaTable = (int *)malloc(26*sizeof(int));
memset(alphaTable, 0, 26*sizeof(int));
int i;
for (i = 0; i < len; i++) {
alphaTable[s[i] - 'a']++;
}
for (i = 0; i < len; i++) {
if (alphaTable[s[i] - 'a'] == 1) {
free(alphaTable);
return i;
}
}
free(alphaTable);
return -1;
}
References
https://leetcode.com/problems/first-unique-character-in-a-string/description
网友评论