python's docs

array 02: fist not repeating character


1. 题目

Note: Write a solution that only iterates over the string once and uses O(1) additional memory, since this is what you would be asked to do during a real interview.

Given a string s, find and return the first instance of a non-repeating character in it. If there is no such character, return '_'.

Example

  • For s = "abacabad", the output should be
    firstNotRepeatingCharacter(s) = 'c'.
    There are 2 non-repeating characters in the string: 'c' and 'd'. Return c since it appears in the string first.

  • For s = "abacabaabacaba", the output should be
    firstNotRepeatingCharacter(s) = '_'.
    There are no characters in this string that do not repeat.

Input/Output

  • [time limit] 4000ms (py)
  • [input] string s
    A string that contains only lowercase English letters.
    Guaranteed constraints:
    1 ≤ s.length ≤ 105.

  • [output] char
    The first non-repeating character in s, or '_' if there are no characters that do not repeat.


2. 解法

个人解法

def firstNotRepeatingCharacter(s):
    records = {}
    for i in range(0, len(s)):
        char = s[i]
        if not char in records:
            records[char] = [i,0]
        else:
            records[char][1] += 1

    not_repeat_records = {i: j[0] for i, j in records.items() if j[1] == 0}
    if not_repeat_records:
        first_not_repeat_record = sorted(not_repeat_records.items(), key=lambda x: x[1])
        first_not_repeat_char = first_not_repeat_record[0][0]
        return first_not_repeat_char
    else:
        return "_"

精品解法

def firstNotRepeatingCharacter(s):
    for c in s:
        if s.find(c) == s.rfind(c):
            return c
    return '_'

不重复的字符有个特点,从左边数第一个和右边数第一个的index值是相同的,因为c是s中轮询而来,必然存在在s中,所以也可以使用.index,.rindex来替代.find,.rfind