LeetCode#387. First Unique Character in a String

发表于 | 分类于 ， ，

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.

分析

通过之前的练习LeetCode#242，很容易就能想到使用数组来记录字母出现的次数，然后找到字符串中，第一个出现次数为1的字符。如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int unique(s)  // s is the target string
  if (s = null)
    return -1

  count = new int[26]
  chars = s.toCharArray()
  for (c in chars)
    count[c - 'a']++

  for (i = 0; i < chars.length; i++)
    if (count[chars[i] - 'a']-- = 0)
      return i

  return -1

上述答案还可以通过消除减法来降低耗时。因为题目规定字符串中只包含小写字母，因此可以不考虑扩展ASCII码，也就是创建一个长度为128的数组，从而避免减法。

另一种解法

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
int unique(s)   // s is the target string
  if (s = null)
    return -1

  chars = s.toCharArray()
  int out = chars.length
  for (c = 'a' to 'z')   // c is a char variable
    index = -1
    for (i = 0; i < chars.length; i++)
      if (chars[i] = c)
        index = i
        break

    if (index = -1)
      continue

    lastIndex = -1
    for (i = (chars.length - 1); i >= 0; i--)
      if (chars[i] = c)
        lastIndex = i
        break

    if (index = lastIndex)
      out = min(index, out)

  return out == chars.length ? -1 : out

这种解法是通过找到每个字母第一次出现的位置和最后一次出现的位置，并将这两个位置进行对比，如果一样就说明只出现了一次。在LeetCode的这道题中，这种解法的速度会更快。不过在极端情况下，这种解法速度会降低到26 * s.length()，而第一种解法永远只需要2 * s.length()次。