字符串解题

发表于 | 分类于
字数统计: 1.3k | 阅读时长 ≈ 5

字符串相关题_python版

最长无重复字符子串长度

题目：给定一个字符串，请找出其中无重复字符的最长子字符串。例如，在”abcabcbb”中，其无重复字符的最长子字符串是”abc”，其长度为 3。

思路：遍历字符串中的每一个元素。借助一个辅助键值对来存储某个元素最后一次出现的下标。用一个整形变量存储当前无重复字符的子串开始的下标。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
# 分析 a b c d e f g d 此时从最近重复的前一个字符d的后一位开始记，即e标记为start。此时继续取下一个数， 例如a，它的前一个字符下标为d[s[i]]=0，若d[s[i]]<start，则不需要更新start,否则更新start。新的无重复子串变为e f g d a
class Solution:
    """
    @param: s: a string
    @return: an integer
    """
    def lengthOfLongestSubstring(self, s):
        # write your code here
        res = 0
        if s is None or len(s) == 0:
            return res
        d = {} # 存储某个元素最后一次出现的下标
        tmp = 0 # 存储每次循环中最长的子串长度
        start = 0  # 记录最近重复字符所在的位置+1
        for i in range(len(s)): # 下标
            # 判断当前字符是否在字典中和当前字符的下标是否大于等于最近重复字符的所在位置
            if s[i] in d and d[s[i]] >= start: # 这里的d[s[i]]为前一个重复的下标
                start = d[s[i]] + 1
            tmp = i - start + 1
            d[s[i]] = i
            res = max(res, tmp)
        return res

最长回文字符串

思路一：中心扩展法。根据回文的特性，显然所有的回文串都是对称的。长度为奇数回文串以最中间字符的位置为对称轴左右对称，而长度为偶数的回文串的对称轴在中间两个字符之间的空隙。可否利用这种对称性来提高算法效率呢？答案是肯定的。我们知道整个字符串中的所有字符，以及字符间的空隙，都可能是某个回文子串的对称轴位置。可以遍历这些位置，在每个位置上同时向左和向右扩展，直到左右两边的字符不同，或者达到边界。对于一个长度为n的字符串，这样的位置一共有n+n-1=2n-1个 ，时间复杂度O(n^2)

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
class Solution(object):
    def longestPalindrome(self, s):
        str_length = len(s)
        max_length = 0   # 记录最大字符串长度,不是对称长度
        start = 0  # 记录位置
        for i in range(str_length): # 当前下标位置
            # 对称位置在对称轴间隙，偶数
            if i - max_length >= 1 and s[i-max_length-1: i+1] == s[i-max_length-1: i+1][::-1]:
                # 记录当前开始位置
                start = i - max_length - 1
                max_length += 2
                continue
            # 对称位置在对称字符，奇数
            if i - max_length >= 0 and s[i-max_length: i+1] == s[i-max_length: i+1][::-1]:
                start = i - max_length
                max_length += 1
        # 返回最长回文子串
        return s[start: start + max_length]


if __name__ == '__main__':
    s = "babad"
    # s = "cbbd"
    sl = Solution()
    print(sl.longestPalindrome(s))

思路二：马拉车算法

看这篇

KMP算法

过程描述看这篇

其实就是,对模式串p进行预处理,得到前后缀的部分匹配表,使得我们可以借助已知信息,算出可以右移多少位.即 kmp = 朴素匹配 + 移动多位.

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
27
28
29
30
31
32
33
34
35
#KMP
    def kmp_match(self, s, p):  
        m = len(s)
        n = len(p)  
        cur = 0  # 起始指针cur，累积移动数  
        table = self.partial_table(p)  
        while cur <= m-n: # 长度不够就终止  
            for i in range(n):  # 一次p从头开始匹配的长度 
                if s[i+cur] != p[i]:  
                    # 移动位数 = 已匹配的字符数 - 对应的部分匹配值
                    # 有了部分匹配表,我们不只是单纯的1位1位往右移,可以一次移动多位  
                    cur += max(i - table[i-1], 1) 
                    break  
            else: # 执行了break就不会执行这句，相当于for循环里所有都满足 s[i+cur] == p[i]
                return cur # 返回匹配开始的位置
        return -1  # 匹配失败

    #部分匹配表  
    def partial_table(self, p):  
        '''''partial_table("ABCDABD") -> [0, 0, 0, 0, 1, 2, 0]'''  
        prefix = set()  
        table = [0]  
        for i in range(1, len(p)):  # 从1开始进行前后缀比较  
            prefix.add(p[:i])  # 前缀每次累加就行
            postfix = set()
            for j in range(1, i+1):  # i+1 因为i需要包括
                postfix.add(p[j:i+1]) 
            # print(prefix, postfix)
            # print(prefix&postfix, len(prefix&postfix))
            # table.append(len((sorted((prefix&postfix),key = len)or {''}).pop()))
            if prefix&postfix:
                table.append(max(map(len,prefix&postfix)))
            else:
                table.append(0)
        return table

字符串去重

1
string = 'abc123456ab2s'r = ''.join(x for i, x in enumerate(string) if string.index(x) == i)

统计一个字符串中英文字母、空格、数字的个数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#!/usr/bin/python
# -*- coding: UTF-8 -*-
 
import string
s = raw_input('请输入一个字符串:\n')
letters = 0
space = 0
digit = 0
others = 0
for c in s:
    if c.isalpha():
        letters += 1
    elif c.isspace():
        space += 1
    elif c.isdigit():
        digit += 1
    else:
        others += 1
print 'char = %d,space = %d,digit = %d,others = %d' % (letters,space,digit,others)
-------------Thanks for Reading!-------------