python algorithms string

Posted on | In | | Visitors: ℃
Words count in article: 1.5k | Reading time ≈ 7

1.1 旋转字符串

题目描述

给定一个字符串，要求把字符串前面的若干个字符移动到字符串的尾部，如把字符串“abcdef”前面的2个字符’a’和’b’移动到字符串的尾部，使得原字符串变成字符串“cdefab”。请写一个函数完成此功能，要求对长度为n的字符串操作的时间复杂度为 O(n)，空间复杂度为 O(1)。

方法：三步反转法

对于这个问题，换一个角度思考一下。

将一个字符串分成X和Y两个部分，在每部分字符串上定义反转操作，如X^T，即把X的所有字符反转（如，X=”abc”，那么X^T=”cba”），那么就得到下面的结论：(X^TY^T)^T=YX，显然就解决了字符串的反转问题。

例如，字符串 abcdef ，若要让def翻转到abc的前头，只要按照下述3个步骤操作即可：

  1. 首先将原字符串分为两个部分，即X:abc，Y:def；
  2. 将X反转，X->X^T，即得：abc->cba；将Y反转，Y->Y^T，即得：def->fed。
  3. 反转上述步骤得到的结果字符串X^TY^T，即反转字符串cbafed的两部分（cba和fed）给予反转，cbafed得到defabc，形式化表示为(X^TY^T)^T=YX，这就实现了整个反转。

代码则可以这么写： 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#反转字符串
def ReverseString(s,left,right):
    s = list(s)
    while(left < right):
        s[left], s[right] = s[right], s[left]
        left += 1
        right -= 1
    s = ''.join(s)
    return s
def leftRotateString(s, n, m):
    m %= n  #若要左移动大于n位，那么和%n 是等价的
    s = ReverseString(s,0,m-1)
    s = ReverseString(s,m,n-1)
    s = ReverseString(s,0,n-1)
    print(s)

s = "123456"
leftRotateString(s,len(s),4)
#运行结果：  561234

1.2 字符串匹配

​ 连续子串在主串中匹配位置,返回第一个匹配的index：如

​ main_string: ‘thequickbrownfoxjumpsoverthelazydog’

​ pattern_string: ‘jump’

​ result: 16

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
36
37
38
39
40
41
42
43
44
45
46
47
48
def simple_hash(s, start, end):
    """
    计算子串的哈希值
    每个字符取acs-ii码后求和
    :param s:
    :param start:
    :param end:
    :return:
    """
    assert start <= end

    ret = 0
    for c in s[start: end+1]:
        ret += ord(c)
    return ret


def rk(main, pattern):
    n = len(main)
    m = len(pattern)

    if n <= m:
        return 0 if pattern == main else -1

    # 子串哈希值表
    hash_memo = [None] * (n-m+1)
    hash_memo[0] = simple_hash(main, 0, m-1)
    print(hash_memo[0])#
    for i in range(1, n-m+1):
        hash_memo[i] = hash_memo[i-1] - simple_hash(main, i-1, i-1) + simple_hash(main, i+m-1, i+m-1)
    print(hash_memo)
    # 模式串哈希值
    hash_p = simple_hash(pattern, 0, m-1)
    print(hash_p)
    for i, h in enumerate(hash_memo):
        # 可能存在哈希冲突
        if h == hash_p:
            if pattern == main[i:i+m]:
                return i
            else:
                continue
    return -1
    
print('--- search ---')
m_str = 'thequickbrownfoxjumpsoverthelazydog'
p_str = 'jump'
print('[rk] result:', rk(m_str, p_str))
#[rk] result: 16

1.3 各种字符串算法（easy）

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
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
#1. 字符串循环移位包含
def string_in():
    s1 = 'CDAA'
    s2 = 'AABCD'

    #方法一
    def string_in1():
        res = False
        for idx, v in enumerate(s2):
            temp = s2[ idx: ] + s2[ :idx ]
            if s1 in temp:
                res = True
        print(res)
        return res

    # 方法二
    def string_in2( ):
        '''
        s2的翻转是s2s2的子串，因此，s1直接判断s2s2即可
        :return:
        '''
        res = False
        if s1 in s2+s2:
            res = True
        print(res)
        return res
    string_in1()
    string_in2()

#2. 字符串循环移位
def move_k_string():
    '''
    将字符串向右循环移动 k 位。
    将 abcd123 中的 abcd 和 123 单独翻转，
    得到 dcba321，然后对整个字符串进行翻转，得到 123abcd。
    :return:
    '''
    k = 4
    s = 'abcd123'
    temp = str(s[:k])[::-1] + str(s[k:])[::-1]
    print(temp[::-1])


#3. 字符串中单词的翻转
def transer_string():
    #将每个单词翻转，然后将整个字符串翻转。
    s = "I am a student"
    res1 = ' '.join([v[::-1] for v in s[:: -1].split()])
    print(res1)

    s1 = s.split(" ")
    s2 = [v[::-1] for v in s1]
    res2 = ' '.join(s2)[::-1]
    print(res2)

#4. 两个字符串包含的字符是否完全相同
from collections import Counter
def is_different_string():
    s = "anagram"
    t = "nagaram"

    def is_different_str1():
        s1 = Counter(s)
        t1 = Counter(t)
        print(s1==t1)

    def is_different_str2():
       resb = True
       res = [ 0 ] * 26
       for v in s:
           res[ ord(v) - ord("a") ] += 1
       for v in t:
           res[ ord(v) - ord("a") ] -= 1
       for v in res:
           if v != 0:
               resb = False
       print(resb)
    is_different_str1()
    is_different_str2()

#5. 计算一组字符集合可以组成的回文字符串的最大长度
def longestPalindrome():
    #能够构成回文字符串，偶数放两边，奇数的放中间,所以要最大长度，偶数全要，奇数最大即可
    s = "abccccdd"

    s1 = Counter(s)
    print(s1)
    odd_number = []
    even_number = []
    for k,v in s1.items():
        if v%2 == 0:
            even_number.append(v)
        else:
            odd_number.append(v)
    print(sum(even_number) + max(odd_number))


#6. 字符串同构
def isIsomorphic():
    #记录一个字符上次出现的位置，如果两个字符串中的字符上次出现的位置一样，那么就属于同构。
    t, s = "paper", "title"

    res = True
    ti, si = [0]*26, [0]*26
    if len(t) != len(s): print(True)
    for i,v in enumerate(t):
        tn = ord(t[i])-ord('a')
        sn = ord(s[i])-ord('a')
        if ti[tn] != si[sn]:
            res = False
        ti[tn] += 1
        si[sn] += 1
    print(res)

# 7. 回文子字符串个数
def count_sub_string():
    #遍历字符每一个字符，然后重这个字符一奇数和偶数去拓展字符，判断是否相同，如果相同就是回文子串+1
    s = 'cbaac'
    cnt = 0

    def is_count_sub(s, start, end):
        nonlocal cnt
        while((start >= 0 and end <= len(s)-1) and (s[start] == s[end])):
            start -= 1
            end += 1
            cnt += 1

    for i,v in enumerate(s):
        is_count_sub(s,i,i)
        is_count_sub(s,i,i+1)

    print(cnt)

# 8. 判断一个整数是否是回文数
def isPalindrome():
    '''
    要求不能使用额外空间，也就不能将整数转换为字符串进行判断。
    将整数分成左右两部分，右边那部分需要转置，然后判断这两部分是否相等。
    :return:
    '''
    n = 121

    def is_subStr():
        nonlocal n
        if n >= 0 and n < 10:
            return True
        if n % 10 == 0:
            return False

        right = 0
        while(n > right):
            right = right * 10 + n % 10
            n /= 10
        return (n == right or  n == right/10)

    res = is_subStr()
    print(res)


# 9. 统计二进制字符串中连续 1 和连续 0 数量相同的子字符串个数
def countBinarySubstrings():
    # 从第二个字符开始，保留已经遍历的连续字符长度prel，在转折不同字符的时候，
    # 连续相同字符长度curl.即当前连续字符个数为min(curl,prel)

    s = "00110011"
    res,curl,prel = 0, 1, 0
    for i in range(1,len(s)):
        if s[i] == s[i-1]:
            curl += 1
        else:
            prel = curl
            curl = 1
        if(prel >= curl):
            res += 1
    print(res)


if __name__ == '__main__':
    # string_in()
    # move_k_string()
    # transer_string()
    # is_different_string()
    # longestPalindrome()
    # isIsomorphic()
    # count_sub_string()
    # isPalindrome()
    countBinarySubstrings()