1.重复的子字符串
给定一个非空的字符串，判断它是否可以由它的一个子串重复多次构成。给定的字符串只含有小写英文字母，并且长度不超过10000。
示例 1:
输入: “abab”
输出: True
解释: 可由子字符串 “ab” 重复两次构成。
示例 2:
输入: “aba”
输出: False
示例 3:
输入: “abcabcabcabc”
输出: True
解释: 可由子字符串 “abc” 重复四次构成。 (或者子字符串 “abcabc” 重复两次构成。)
用正则去做 /^(\w+)\1+$/即为对应正则表达式
export default (str)=>{
var reg=/^(\w+)\1+$/
return reg.test(str)
}
2.正则表达式匹配
给你一个字符串 s 和一个字符规律 p，请你来实现一个支持 ‘.’ 和 ‘’ 的正则表达式匹配。
‘.’ 匹配任意单个字符
'’ 匹配零个或多个前面的那一个元素
所谓匹配，是要涵盖 整个 字符串 s的，而不是部分字符串。
说明:
s 可能为空，且只包含从 a-z 的小写字母。
p 可能为空，且只包含从 a-z 的小写字母，以及字符 . 和 *。
示例 1:
输入:
s = “aa”
p = “a”
输出: false
解释: “a” 无法匹配 “aa” 整个字符串。
示例 2:
输入:
s = “aa”
p = “a*”
输出: true
解释: 因为 ‘*’ 代表可以匹配零个或多个前面的那一个元素, 在这里前面的元素就是 ‘a’。因此，字符串 “aa” 可被视为 ‘a’ 重复了一次。
示例 3:
输入:
s = “ab”
p = “."
输出: true
解释: ".” 表示可匹配零个或多个（‘*’）任意字符（‘.’）。
示例 4:
输入:
s = “aab”
p = “cab”
输出: true
解释: 因为 ‘*’ 表示零个或多个，这里 ‘c’ 为 0 个, ‘a’ 被重复一次。因此可以匹配字符串 “aab”。
示例 5:
输入:
s = “mississippi”
p = “misisp*.”
输出:
- 一个字符一个字符对比，对比完一个扔掉一组，然后重复刚才的动作
- 三种情况：无模式，有模式*,有模式.
export default (s,p)=>{
let isMatch=(s,p)=>{
// 边界情况，如果s和p都为空，说明处理结束，返回true，否则返回false
if(p.length<=0){
return !s.length
}
// 判断p模式字符串的第一个字符和s字符串的第一个字符是不是匹配
let match=false
if(s.length>0&&(p[0]===s[0]||p[0]==='.')){
match=true
}
// p有模式的，字符后面有*
if(p.length>1&&p[1]==='*'){
// 第一种情况：s*匹配0个字符
// 第二种情况：s*匹配1个字符，递归下去，用来表示s*匹配多个s
return isMatch(s,p.slice(2))||(match && isMatch(s.slice(1),p))
}else{// 字符后面没有*
return match && isMatch(s.slice(1),p.slice(1))
}
}
return isMatch(s,p)
}
3.复原IP地址
给定一个只包含数字的字符串，复原它并返回所有可能的 IP 地址格式。
示例:
输入: “25525511135”
输出: [“255.255.11.135”, “255.255.111.35”]
P由4部分构成，每部分范围0~255（递归）
所有情况都列出来(每个子字符串都可以是一位数到三位数)，然后按条件筛选
export default (str)=>{
// 保存所有符合条件的ip
let r=[]
// 递归函数
let search=(cur,sub)=>{
if(cur.length===4&&cur.join('')===str){
r.push(cur.join('.'))
}else{
for(let i=0,len=Math.min(3,sub.length),tmp;i<len;i++){
tmp=sub.substr(0,i+1)
if(tmp<256){
search(cur.concat([tmp]),sub.substr(i+1))
}
}
}
}
search([],str)
return r
}
- 递归的本质（就是一个while循环，但可以有多个条件或地方调用）
- 每一个处理过程是相同的
- 输入输出是相同的
- 处理次数未知
4.与所有单词相关联的字符串
给定一个字符串 s 和一些长度相同的单词 words。找出 s 中恰好可以由 words 中所有单词串联形成的子串的起始位置。
注意子串要与 words 中的单词完全匹配，中间不能有其他字符，但不需要考虑 words 中单词串联的顺序。
示例 1：
输入：
s = “barfoothefoobarman”,
words = [“foo”,“bar”]
输出：[0,9]
解释：
从索引 0 和 9 开始的子串分别是 “barfoor” 和 “foobar” 。
输出的顺序不重要, [9,0] 也是有效答案。
示例 2：
输入：
s = “wordgoodgoodgoodbestword”,
words = [“word”,“good”,“best”,“word”]
输出：[]
递归循环来计算出所有的words组合，然后匹配字符串即可。
export default (str,words)=>{
// 保存结果
let result=[]
// 记录数组的长度，做边界条件计算
let num=words.length
// 递归函数体
let range=(r,_arr)=>{
if(r.length===num){
result.push(r)
}else{
_arr.forEach((item,idx)=>{
// 当前元素踢出去，留下剩下的
let tmp=[].concat(_arr)
tmp.splice(idx,1)
range(r.concat(item),tmp)
})
}
}
range([], words)
// [0,9,-1]
return result.map(item=>{
return str.indexOf(item.join(''))
}).filter(item=>item!==-1).sort()
}
