KMP算法
例如一个字符串有30W个字符判断是否存在"I am Chinese". 类似这样的查找字符的毫无疑问需要使用KMP.
KMP算法由二个部分组成.
- 获取查找串的部分匹配表PMT
- 源串根据PMT进行回滚 回滚位数 = 已匹配的字符数 - 对应的部分匹配值
PMT
最大匹配数是前缀集合与后缀集合的交集中最长元素的长度
// abababc
function PMT(str){
let next = [], n = 0;
next[0] = 0;
for (let i = 1; i < str.length; i++) {
while (n > 0 && str[i] != str[n]) { // 当前字符不等于第n+1位字符 那么n为次大匹配格式再进行判断
n = next[n-1]
}
if (str[i] == str[n]) {
n++;
}
next[i] = n;
}
return next;
}
}
PMT("ababa") => [0, 0, 1, 2, 3]
while (n > 0 && str[i] != str[n])这段代码可能比较难理解. 主要是根据next(n-1)最大匹配数来计算next(n). 如果str[i] == str[n]那么next[n] = next[n-1]+1, 否则将n设置为次大匹配数next[n-1]; 如果还是理解不了可以看知乎
回滚
如果没有匹配上，源串会进行回滚回滚位数 = 已匹配的字符数 - 对应的部分匹配值
function KMP(){
const next = PMT(k);
let index = -1;
for (let i = 0; i < str.length; i++) {
for (let j = 0; j < k.length; j++){
if (str[i] == k[j]) { // 如果相等
if (j == k.length-1) { // 完全匹配
index = i-k.length+1
break;
}
i++;
} else {
i = i-j+next[j]
break;
}
}
}
if (index == -1) {
return false;
}
}
字符串压缩
设计一种方法，通过给重复字符计数来进行基本的字符串压缩。 例如，字符串 aabcccccaaa 可压缩为 a2b1c5a3 。而如果压缩后的字符数不小于原始的字符数，则返回原始的字符串。
const compress = function (str) {
if (!str.length) {
return str;
}
let newstr = str[0], num = 1;
for (let i = 1; i < str.length; i++) {
if (str[i] == str[i-1]) {
num++;
if (i == str.length - 1) {
newstr += num
}
} else {
newstr += num;
newstr += str[i]
num =1;
}
}
if (newstr.length >= str.length) {
return str
}
return newstr
}
最长无重复字符的子串
给定一个字符串，请找出其中无重复字符的最长子字符串。 例如，在"abcabcbb"中，其无重复字符的最长子字符串是"abc"，其长度为 3。
const lengthOfLongestSubstring = function (str) {
let max = 0,
i = 0,
index = 0,
hash = {};
while (i < str.length) {
let letter = str[i];
if (!hash[letter]){
hash[letter] = true;
if (i-index+1 >= max){
max = i-index+1
}
} else {
while (index < i) {
if (str[index] != letter) {
hash[str[index]] = false;
index++
} else {
index++;
break
}
}
hash[letter] = true;
}
i++;
}
return max
}
有效回文串
给定一个字符串，判断其是否为一个回文串。只考虑字母和数字，忽略大小写。 例如"A man, a plan, a canal: Panama" 是一个回文。
const isPalindrome = function (str) {
var i = 0, j = str.length-1;
if (str.length == 1) {
return true
}
while (j >= i+1) {
if (!/[\da-zA-z]/.test(str[i])) {
i++
}
if (!/[\da-zA-z]/.test(str[j])) {
j--
}
if ( j >i && str[i].toLowerCase() != str[j].toLowerCase()) {
return false
}
i++; j--;
}
return true
}
}
罗马数字转整数
给定一个罗马数字，将其转换成整数。 回的结果要求在1到3999的范围内。。
const romanToInt = function (str) {
let map = new Map([["I", 1], ["V", 5], ["X", 10], ["L", 50], ["C", 100], ["D", 500], ["M", 1000]]);
let total = 0;
// 左减必须为1位 右减不超过3位
if (str.length == 1) {
return map.get(str[0]);
}
for (let i = 1; i < str.length; i++) {
let rightNum = map.get(str[i]);
let leftNum = map.get(str[i-1]);
if (rightNum > leftNum) {
total += (rightNum-leftNum);
i++;
} else {
total += leftNum;
}
if (i == str.length-1) {
total += map.get(str[i]);
}
}
return total
}
One Edit Distance
给你两个字符串 S 和 T, 判断他们是否只差一步编辑。 例如字符串 s = "aDb", t= "adb"返回true
const isOneEditDistance = function (s, t) {
if (Math.ceil(s.length-t.length) >= 2){
return false;
}
let len = Math.abs(s.length, t.length);
let count = 0; // 调整次数
for (let i = 0, j = 0; i < len ; i++) {
if (s[i] != t[j]) {
count++;
if (count >= 2) {
return false
}
if (s.length > t.length) {
j--
} else if (s.length < t.length) {
i--
}
}
j++;
}
if (count == 1 || (count == 0 && Math.abs(s.length-t.length) == 1)) {
return true;
} else {
return false;
}
}
Find All Anagrams in a String
给定一个字符串 s 和一个 非空字符串 p ，找到在 s 中所有关于 p 的字谜的起始索引。 字符串仅由小写英文字母组成，字符串 s 和 p 的长度不得大于 40,000。 输出顺序无关紧要。
const findAnagrams = (s, p) => {
let indexs = [],
storehash = {},
hash = {}
for (let i = 0; i < p.length; i++) {
let str = p[i];
storehash[str] = storehash[str] ? storehash[str] + 1 : 1;
hash[str] = hash[str] ? hash[str]+1:1
}
let i = 0,
index = -1,
count = 0;
while (i < s.length) {
let char = s[i];
if (hash[char]){
if (index == -1) {
index = i;
}
count++;
hash[char]--;
if (count == p.length) { // 如果count等于0说明满足情况 存储i
indexs.push(index);
hash[s[index]]++;
count = p.length-1;
index++;
}
} else {
if (index != -1 && hash[char] != undefined && (s.length - index) >= p.length) {
while (index < i) { // char溢出了 丢弃前面不为char的字符
if (s[index] === char) {
index++;
break;
} else {
count--;
hash[s[index]]++;
}
index++;
}
} else { // 遇到不在hash中的字符则初始化hash, index和count
hash = Object.assign({}, storehash);
count = 0;
index = -1;
}
}
i++;
}
return indexs
}
