python - 如何对 "Finding first unique character in a string"实现暴力破解

Question

如这里所述: https://leetcode.com/problems/first-unique-character-in-a-string/description/

我在这里尝试了一个但没能完全完成: https://paste.pound-python.org/show/JuPLgdgqceMQYh5kk0Sf/

#Given a string, find the first non-repeating character in it and return it's index. If it doesn't exist, return -1.
#xamples:
#s = "leetcode"
#return 0.

#s = "loveleetcode",
#return 2.
#Note: You may assume the string contain only lowercase letters.

class Solution(object):
    def firstUniqChar(self, s):
        """
        :type s: str
        :rtype: int
        """
        for i in range(len(s)):
            for j in range(i+1,len(s)):
                if s[i] == s[j]:
                    break          
               #But now what. let's say i have complete loop of j where there's no match with i, how do I return i?

我只对蛮力 N^2 解决方案感兴趣，没什么特别的。上述解决方案的想法是启动一个双循环，其中内循环搜索与外循环的字符匹配，如果匹配，则中断内循环并继续外循环的下一个字符。

但问题是，当没有匹配项时我该如何处理，即当我需要将外循环的索引作为第一个唯一索引返回时。

无法完全找到一种优雅的方式来做到这一点，并且可以像处理单个 char 字符串一样处理边缘情况。

Answer 1

遍历每个字符，并检查它是否出现在以下任何字符中。我们需要跟踪我们已经看到的字符，以避免陷入边缘情况。试试这个，这是一个 O(n^2) 解决方案:

def firstUniqChar(s):
    # store already seen chars
    seen = []
    for i, c in enumerate(s):
        # return if char not previously seen and not in rest
        if c not in seen and c not in s[i+1:]:
            return i
        # mark char as seen
        seen.append(c)
    # no unique chars were found
    return -1

为了完整起见，这里有一个O(n) 的解决方案:

def firstUniqChar(s):
    # build frequency table
    freq = {}
    for i, c in enumerate(s):
        if c not in freq:
            # store [frequency, index]
            freq[c] = [1, i]
        else:
            # update frequency
            freq[c][0] += 1
    # find leftmost char with frequency == 1
    # it's more efficient to traverse the freq table
    # instead of the (potentially big) input string
    leftidx = float('+inf')
    for f, i in freq.values():
        if f == 1 and i < leftidx:
            leftidx = i
    # handle edge case: no unique chars were found
    return leftidx if leftidx != float('+inf') else -1

例如:

firstUniqChar('cc')
=> -1
firstUniqChar('ccdd')
=> -1
firstUniqChar('leetcode')
=> 0
firstUniqChar('loveleetcode')
=> 2