string部分刷题笔记（初次编辑版）
17.Letter Combinations of a Phone Number
22 这题用回溯，我不会回溯
434 python的split()方法默认是判断空格，但是为什么split(‘’)不行呢
Given a string, find the length of the longest substring without repeating characters.
Examples:
Given “abcabcbb”, the answer is “abc”, which the length is 3.
Given “bbbbb”, the answer is “b”, with the length of 1.
Given “pwwkew”, the answer is “wke”, with the length of 3. Note that the answer must be a substring, “pwke” is a subsequence and not a substring.
Hash Table & Two Pointers & String
最长无重复子串问题
双指针，滑动窗口
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution (object) :
def lengthOfLongestSubstring (self, s) :
"""
:type s: str
:rtype: int
"""
res = 0
start = end = 0
char_set = set()
while start < len(s) and end < len(s):
if s[end] in char_set:
res = max(res,end - start)
char_set.remove(s[start])
start +=1
else :
char_set.add(s[end])
end += 1
return max(res,end - start)
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
* @param {string} s
* @return {number}
*/
* http://www.jianshu.com/p/b97ba06b488a
* https://msdn.microsoft.com/library/dn251547(v=vs.94).aspx（介绍set对象）
*/
var lengthOfLongestSubstring = function (s )
var len = s.length,
max = 0 ,
start = 0 ,
i,
chars = new Set (),
curChar;
for (i = 0 ; i < len; i++){
curChar = s.charAt(i);
if (chars.has(curChar)){
while (start < i && s.charAt(start) !== curChar){
chars.delete(s.charAt(start));
start++;
}
start++;
}else {
chars.add(curChar);
max = Math .max(max,i - start + 1 );
}
}
return max;
};
最长回文子串问题
我们想想，如果一段字符串是回文，那么以某个字符为中心的前缀和后缀都是相同的，例如以一段回文串 “aba” 为例，以 b 为中心，它的前缀和后缀都是相同的，都是 a。
那么，我们是否可以可以枚举中心位置，然后再在该位置上用扩展法，记录并更新得到的最长的回文长度呢？答案是肯定的，参考代码
这个讲了降复杂度的过程
求子串：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution (object) :
def longestPalindrome (self, s) :
"""
:type s: str
:rtype: str
"""
res = ""
for i in xrange(len(s)):
tmp = self.helper(s, i, i)
if len(tmp) > len(res):
res = tmp
tmp = self.helper(s, i, i+1 )
if len(tmp) > len(res):
res = tmp
return res
def helper (self, s, l, r) :
while l >= 0 and r < len(s) and s[l] == s[r]:
l -= 1 ; r += 1
return s[l+1 :r]
求子串长度：
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
class Solution (object) :
def longestPalindrome (self, s) :
"""
:type s: str
:rtype: str
"""
arr = list(s)
n = len(arr)
if n == 0 :
return ""
max,c = 0 ,0
for i in range(n):
tmp = min(i,n-i)
for j in range(tmp):
if s[i - j] != s[i + j]:
break
c = j * 2 + 1
if c > max:
max = c
tmp = min(i,n-i-1 )
for j in range(tmp):
if s[i - j] != s[i + j + 1 ]:
break ;
c = j * 2 + 2
if c > max:
max = c
return max
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution (object) :
def convert (self, s, numRows) :
"""
:type s: str
:type numRows: int
:rtype: str
"""
size = numRows * 2 -2
length = len(s)
result = ''
if numRows == 1 :
return s
for i in range(numRows):
for j in range(i,length,size):
print j
result += s[j]
if i != 0 and i != numRows -1 :
mid = j + size - 2 * i
if mid < length:
result += s[mid]
return result
j的值为
所以此题关键在size = numRows * 2 -2
题目的要求：
首先需要丢弃字符串前面的空格；
然后可能有正负号（注意只取一个，如果有多个正负号，那么说这个字符串是无法转换的，返回 0。比如测试用例里就有个 “+-2”）；
字符串可以包含 0~9 以外的字符，如果遇到非数字字符，那么只取该字符之前的部分，如 “-00123a66” 返回为 “-123”；
如果超出 int 的范围，返回边界值（2147483647 或 - 2147483648）
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
class Solution (object) :
def myAtoi (self, str) :
"""
:type str: str
:rtype: int
"""
str = str.strip()
length = len(str)
if str == "" :
return 0
sign = 1
i = 0
if str[i] == '+' :
i += 1
elif str[i] == '-' :
i += 1
sign = -1
res = 0
MaxInt = (1 << 31 ) - 1
for i in range(i,length):
if str[i] < '0' or str[i] > '9' :
break
res = res * 10 + int(str[i])
if res > MaxInt:
break
if sign == -1 :
res *= -1
if res > MaxInt:
return MaxInt
if res < MaxInt * -1 :
return MaxInt * -1 - 1
return res
Given an integer, convert it to a roman numeral.
Input is guaranteed to be within the range from 1 to 3999.
罗马数字共有 7 个，即 I（1）、V（5）、X（10）、L（50）、C（100）、D（500）和 M（1000）。
罗马数字中没有 “0”。
重复次数：一个罗马数字最多重复 3 次。
右加左减：
在较大的罗马数字的右边记上较小的罗马数字，表示大数字加小数字。
在较大的罗马数字的左边记上较小的罗马数字，表示大数字减小数字。
左减的数字有限制，仅限于 I、X、C，且放在大数的左边只能用一个。
(*) V 和 X 左边的小数字只能用 Ⅰ
(*) L 和 C 左边的小数字只能用 X
(*) D 和 M 左 边的小数字只能用 C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
/**
* @param {number} num
* @return {string}
*/
var intToRoman = function(num) {
var dict = ["M" ,"CM" ,"D" ,"CD" ,"C" ,"XC" ,"L" ,"XL" ,"X" ,"IX" ,"V" ,"IV" ,"I" ],
val = [1000 ,900 ,500 ,400 ,100 ,90 ,50 ,40 ,10 ,9 ,5 ,4 ,1 ],
len = 13 ,
result = '' ,
count,
i;
for (i = 0 ;i < len; i++){
if (num >= val[i]){
count = Math.floor(num/val[i]);
while (count > 0 ){
result += dict[i];
count--;
}
num %= val[i];
}
}
return result;
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution (object) :
def romanToInt (self, s) :
"""
:type s: str
:rtype: int
"""
length = len(s)
if length == 0 :
return 0
map = {}
map['I' ] = 1 ;
map['X' ] = 10 ;
map['C' ] = 100 ;
map['M' ] = 1000 ;
map['V' ] = 5 ;
map['L' ] = 50 ;
map['D' ] = 500
res = 0
for i in range(length):
res += map[s[i]]
if i > 0 and map[s[i]] > map[s[i - 1 ]]:
res -= 2 * map[s[i-1 ]];
return res
Write a function to find the longest common prefix string amongst an array of strings.
2 个字符串的最长公共前缀，其长度肯定不会超过最短的字符串的长度，设最短的字符串长度为 n，那么只要比较这 2 个字符串的前 n 个字符即可。
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
* @param {string[]} strs
* @return {string}
*/
var longestCommonPrefix = function (strs )
var len = strs.length,
len1,
curChar,
i,j;
if (len ===0 ){
return '' ;
}
len1 = strs[0 ].length;
for (i = 0 ;i < len1;i++){
curChar = strs[0 ].charAt(i);
for (j = 1 ;j < len;j++){
if (strs[j].charAt(i) !== curChar){
return i === 0 ? '' :strs[0 ].substr(0 ,i);
}
}
}
return strs[0 ];
};
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
// version 1
class Solution :
def letterCombinations (self, digits) :
def dfs (num, string, res) :
if num == length:
res.append(string)
return
for letter in dict[digits[num]]:
dfs(num+1 , string+letter, res)
dict = {'2' :['a' ,'b' ,'c' ],
'3' :['d' ,'e' ,'f' ],
'4' :['g' ,'h' ,'i' ],
'5' :['j' ,'k' ,'l' ],
'6' :['m' ,'n' ,'o' ],
'7' :['p' ,'q' ,'r' ,'s' ],
'8' :['t' ,'u' ,'v' ],
'9' :['w' ,'x' ,'y' ,'z' ]
}
res = []
length = len(digits)
if length == 0 :
return res
dfs(0 , '' , res)
return res
// version 2
class Solution (object) :
'''
题意：输出电话号码对应的所有可能的字符串
可以递归或直接模拟
'''
def letterCombinations (self, digits) :
chr = ["" , "" , "abc" , "def" , "ghi" , "jkl" , "mno" , "pqrs" , "tuv" , "wxyz" ]
res = []
for i in range(0 , len(digits)):
num = int(digits[i])
tmp = []
for j in range(0 , len(chr[num])):
if len(res):
for k in range(0 , len(res)):
tmp.append(res[k] + chr[num][j])
else :
tmp.append(str(chr[num][j]))
res = copy.copy(tmp)
return res
递归问题得重写啊朋友
Given a string containing just the characters ‘(‘, ‘)’, ‘{‘, ‘}’, ‘[‘ and ‘]’, determine if the input string is valid.
The brackets must close in the correct order, “()” and “()[]{}” are all valid but “(]” and “([)]” are not.
这一题是典型的使用压栈的方式解决的问题，题目中还有一种 valid 情况没有说明，需要我们自己考虑的，就是 “({[]})” 这种层层嵌套但可以完全匹配的，也是 valid 的一种。
解题思路是这样的：我们对字符串 S 中的每一个字符 C，如果 C 不是右括号，就压入栈 stack 中。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution (object) :
'''
题意：输入一个只包含括号的字符串，判断括号是否匹配
模拟堆栈，读到左括号压栈，读到右括号判断栈顶括号是否匹配
'''
def isValidParentheses (self, s) :
stack = []
for ch in s:
if ch == '{' or ch == '[' or ch == '(' :
stack.append(ch)
else :
if not stack:
return False
if ch == ']' and stack[-1 ] != '[' or ch == ')' and stack[-1 ] != '(' or ch == '}' and stack[-1 ] != '{' :
return False
stack.pop()
return not stack
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
* @param {string} s
* @return {boolean}
*/
var isValid = function (s )
if (s === null ){
return false ;
}
var stack = [],
sets = {'(' :')' ,'{' :'}' ,'[' :']' },
len = s.length,
cur,
stackTop,
i;
for (i = 0 ; i < len; i++){
cur = s.charAt(i);
if (sets.hasOwnProperty(cur)){
stack.push(cur);
} else {
if (stack.length === 0 ){
return false ;
} else {
stackTop = stack.pop();
if (sets[stackTop] !== cur){
return false ;
}
}
}
}
if (stack.length === 0 ){
return true ;
} else {
return false ;
}
};
Implement strStr().
Returns the index of the first occurrence of needle in haystack, or -1 if needle is not part of haystack.
尼玛，这题的题面我读了八遍
实现 strstr(). 返回 needle(关键字) 在 haystack(字符串) 中第一次出现的位置，如果 needle 不在 haystack 中，则返回 - 1。
针对此题的较好解决方案是kmp
我用的，显然是循环遍历，唉，做的不是很顺利
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
* @param {string} haystack
* @param {string} needle
* @return {number}
*/
var strStr = function (haystack, needle )
var i = 0 ,
len1 = haystack.length,
len2 = needle.length;
if (len2 === 0 ){
return 0 ;
}
if (len1 ===0 || len1 < len2){
return -1 ;
}
for (i =0 ; i <= len1-len2; i++){
if (haystack.substring(i,i+len2) === needle){
return i;
}
}
return -1 ;
};
这道题是判断关键字在字符串中第一次的位置
还可以出题要求判断字符串 B 中所有字母是否都在字符串 A 里
字符串包含问题：
暴力破解，两层循环
先排序再遍历，不过这样就改变下标了
对应质数再相除
签名（这个不适合我的智商）
The count-and-say sequence is the sequence of integers beginning as follows:
1 is read off as “one 1” or 11.
第 i+1 个字符串是第 i 个字符串的读法，第一字符串为 “1”
比如第四个字符串是 1211，它的读法是 1 个 1、1 个 2,2 个 1，因此第五个字符串是 111221。
第五个字符串的读法是：3 个 1、2 个 2、1 个 1，因此第六个字符串是 312211
这是一个迭代的过程，当前行数的读法是取决于上一行的字符串的，所以需要
accum记录当前行，s记录当前行的值
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
* @param {number} n
* @return {string}
*/
var countAndSay = function (n )
function interpret (s,accum,sum )
var times = 1 ,
len = s.length,
num = s.charAt(0 ),
i,
result = "" ;
for (i = 1 ; i < len; i++){
if (s.charAt(i) !== num){
result += times + num;
num = s.charAt(i);
times = 1 ;
}else {
times++;
}
}
if (accum === 1 ){
result = '1' ;
}else {
result += times + num;
}
if (accum === sum){
return result;
}else {
return interpret(result,accum+1 ,sum);
}
}
return interpret('1' ,1 ,n);
};
其实我们可以发现字符串中永远只会出现 1,2,3 这三个字符，假设第 k 个字符串中出现了 4，那么第 k-1 个字符串必定有四个相同的字符连续出现，假设这个字符为 1，则第 k-1 个字符串为 x1111y。第 k-1 个字符串是第 k-2 个字符串的读法，即第 k-2 个字符串可以读为 “x 个 1,1 个 1,1 个 y” 或者 “ 个 x,1 个 1,1 个 1,y 个 ”，这两种读法分别可以合并成 “x+1 个 1,1 个 y” 和 “ 个 x，2 个 1，y 个 ”，代表的字符串分别是 “(x+1)11y” 和 “x21y”，即 k-1 个字符串为 “(x+1)11y” 或 “x21y”，不可能为 “x1111y”.
Given a string s consists of upper/lower-case alphabets and empty space characters ‘ ‘, return the length of last word in the string.
If the last word does not exist, return 0.
Note: A word is defined as a character sequence consists of non-space characters only.
For example,
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
* @param {string} s
* @return {number}
*/
var lengthOfLastWord = function (s )
var arr = s.split(' ' ),
len = arr.length,
i;
for (i = len - 1 ;i >= 0 ;i--){
if (arr[i] !== '' && arr[i] !== ' ' ){
return arr[i].length;
}
}
return 0 ;
};
1
2
3
4
5
6
7
class Solution (object) :
def lengthOfLastWord (self, s) :
"""
:type s: str
:rtype: int
"""
return len(s.strip().split(' ' )[-1 ])
Given two binary strings, return their sum (also a binary string).
For example,
二进制加法都是从最低位（从右加到左）。所以对两个字符串要从最后一位开始加，如果遇见长度不一的情况，就把短的字符串高位补 0.
每轮计算要加上进位，最后跳出循环后要坚持进位是否为 1，以便更新结果
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
* @param {string} a
* @param {string} b
* @return {string}
*/
var addBinary = function (a, b )
var len1 = a.length,
len2 = b.length,
overflow = 0 ,
char1,
char2,
result = '' ,
i,
j,
curval;
for (i = len1 -1 , j = len2 - 1 ; i >= 0 && j >= 0 ; i--,j--){
char1 = parseInt (a.charAt(i));
char2 = parseInt (b.charAt(j));
curval = char1 + char2 + overflow;
if (curval > 1 ){
overflow = 1 ;
curval = curval - 2 ;
}else {
overflow = 0 ;
}
result = curval + result;
}
while (i >= 0 ){
char1 = parseInt (a.charAt(i));
curval = char1 + overflow;
if (curval > 1 ){
overflow = 1 ;
curval = curval - 2 ;
}else {
overflow = 0 ;
}
result = curval + result;
i--;
}
while (j >= 0 ){
char2 = parseInt (b.charAt(j));
curval = char2 + overflow;
if (curval > 1 ){
overflow = 1 ;
curval = curval - 2 ;
}else {
overflow = 0 ;
}
result = curval + result;
j--;
}
if (overflow === 1 ){
result = "1" + result;
}
return result;
};
判断这个字符串是不是回文的，先去掉空格，然后双指针遍历
Given a string, determine if it is a palindrome, considering only alphanumeric characters and ignoring cases.
For example,
Note:
For the purpose of this problem, we define empty string as valid palindrome.
two point & string
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution (object) :
def isPalindrome (self, s) :
"""
:type s: str
:rtype: bool
"""
length = len(s)
begin, end = 0 , length - 1
while begin < end:
while begin < end and not s[begin].isalpha() and not s[begin].isdigit():
begin += 1
while begin < end and not s[end].isalpha() and not s[end].isdigit():
end -= 1
if begin < end and s[begin].lower() != s[end].lower():
return False
else :
begin += 1
end -= 1
return True
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
* @param {string} s
* @return {boolean}
*/
var isPalindrome = function (s )
var len = s.length,
str,
i;
if (len === 0 ){
return true ;
}
str = s.replace(/\W/g ,'' ).toLowerCase();
len = str.length;
if (len === 0 ){
return true ;
}
for (i = 0 ;i < len/2 ;i++){
if (str.charAt(i) !== str.charAt(len - 1 - i)){
return false ;
}
}
return true ;
};
Compare two version numbers version1 and version2.
You may assume that the version strings are non-empty and contain only digits and the . character.
Here is an example of version numbers ordering:
思路就是把字符串按照小数点分割开来，然后逐个比较
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
/**
* @param {string} version1
* @param {string} version2
* @return {number}
*/
var compareVersion = function(version1, version2) {
var arr1 = version1.split('.'),
arr2 = version2.split('.'),
len1 = arr1.length,
len2 = arr2.length,
a,
b,
i,
j;
for(i = 0; i < len1 && i < len2; i++){
a = parseInt(arr1[i]);
b = parseInt(arr2[i]);
if(a > b){
return 1;
}else if(a < b){
return -1;
}
}
if(len1 < len2){
for(j = i; j < len2; j++){
b = parseInt(arr2[j]);
if(b > 0){
return -1;
}
}
}else if(len1 > len2){
for(j = i; j < len1;j++){
a = parseInt(arr1[j]);
if(a > 0){
return 1;
}
}
}
return 0;
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution (object) :
def compareVersion (self, version1, version2) :
"""
:type version1: str
:type version2: str
:rtype: int
"""
versions1 = [int(i) for i in version1.split('.' )]
versions2 = [int(i) for i in version2.split('.' )]
for i in range(max(len(versions1), len(versions2))):
if i < len(versions1):
v1 = versions1[i]
else :
v1 = 0
if i < len(versions2):
v2 = versions2[i]
else :
v2 = 0
if v1 < v2:
return -1
elif v1 > v2:
return 1
return 0
Write a function that takes a string as input and returns the string reversed.
Example:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
* @param {string} s
* @return {string}
*/
* js字符串转换成数组
* var a = "abc";a.split("");//["a","b","c"]
* js数组转换成字符串
* var a = ["a","b","c"];a.join("");//"abc"
*/
var reverseString = function (s )
var arr = s.split("" ).reverse().join("" );
return arr;
};
1
2
3
4
5
6
7
class Solution (object) :
def reverseString (self, s) :
"""
:type s: str
:rtype: str
"""
return s[::-1 ]
Write a function that takes a string as input and reverse only the vowels of a string.
Example 1:
Example 2:
Note:
two points & string
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution (object) :
def reverseVowels (self, s) :
"""
:type s: str
:rtype: str
"""
vowels = set(list("aeiouAEIOU" ))
arr = list(s)
i = 0
j = len(arr) -1
while i<j:
if arr[i] in vowels and arr[j] in vowels:
arr[i],arr[j] = arr[j],arr[i]
i += 1
j -= 1
if arr[i] not in vowels:
i += 1
if arr[j] not in vowels:
j -= 1
return '' .join(arr)
Given an arbitrary ransom note string and another string containing letters from all the magazines, write a function that will return true if the ransom note can be constructed from the magazines ; otherwise, it will return false.
Each letter in the magazine string can only be used once in your ransom note.
Note:
1
2
3
canConstruct("a", "b") -> false
canConstruct("aa", "ab") -> false
canConstruct("aa", "aab") -> true
两个字符串，第一个字符串中的字母都是从第二个字符串中取得的。可以使用 hashmap，将第一个字符串读取入 hashmap,key 是字符，value 是对应该字符的个数。
然后遍历第二个字符串，对 hashmap 进行操作，依次对 hashmap 中含有的字符个数进行 –，如果个数 <0, 则说明 map 中 (即第一个字符中) 含有的字符，在第二个字符串中没有覆盖到。代码如下。
1
2
3
4
5
6
7
8
9
10
11
class Solution (object) :
def canConstruct (self, ransomNote, magazine) :
"""
:type ransomNote: str
:type magazine: str
:rtype: bool
"""
for i in set(ransomNote):
if ransomNote.count(i) > magazine.count(i):
return False
return True
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution (object) :
def canConstruct (self, ransomNote, magazine) :
"""
:type ransomNote: str
:type magazine: str
:rtype: bool
"""
list(ransomNote).sort()
list(magazine).sort()
length1 = len(ransomNote)
length2 = len(magazine)
if length1 > length2:
return False
for i in ransomNote:
if ransomNote.count(i) > magazine.count(i):
return False
return True
Count the number of segments in a string, where a segment is defined to be a contiguous sequence of non-space characters.
Please note that the string does not contain any non-printable characters.
Example:
1
2
Input: "Hello, my name is John"
Output: 5
1
2
3
4
5
6
7
8
class Solution (object) :
def countSegments (self, s) :
"""
:type s: str
:rtype: int
"""
return len(s.split())
python的split()方法默认是判断空格，但是为什么split(‘’)不行呢
Given a non-empty string check if it can be constructed by taking a substring of it and appending multiple copies of the substring together. You may assume the given string consists of lowercase English letters only and its length will not exceed 10000.
Example 1:
Input: “abab”
Output: True
Explanation: It’s the substring “ab” twice.
Example 2:
Input: “aba”
Output: False
Example 3:
Input: “abcabcabcabc”
Output: True
Explanation: It’s the substring “abc” four times. (And the substring “abcabc” twice.)
Basic idea:
First char of input string is first char of repeated substring
Last char of input string is last char of repeated substring
Let S1 = S + S (where S in input string)
Remove 1 and last char of S1. Let this be S2
If S exists in S2 then return true else false
Let i be index in S2 where S starts then repeated substring length i + 1 and repeated substring S[0: i+1]
上面就是在说，判断一个字符串是不是被重复组成的，加两遍组成字符串1，然后将第一个和最后一个字符串颠倒组成字符串2，判断原字符串在不在字符串2里
太特么机智了
1
2
3
4
5
6
7
8
9
10
11
def repeatedSubstringPattern (self, str) :
"""
:type str: str
:rtype: bool
"""
if not str:
return False
ss = (str + str)[1 :-1 ]
return ss.find(str) != -1
