全文共14056字,预计学习时长36分钟
字符串是一系列字符,由常数或变量构成。它是编程语言中必不可少的数据类型。本文中将重点关注JavaScript字符串操作,但其原理和算法也可应用于其他语言。
参加技术面试时,面试官常常会关注以下内容:
· 编程技术
· 语言能力
· 解题技巧
本文不仅可以让你成功通过技术面试,对日常编码也很有用。代码要点格式中,我们列出了JavaScript字符串的几点重要特性,这是编程技能的基础。其中包括存在了20年的属性和方法,也涵盖ES2021中的特性。如有不清楚之处,可以有针对性地查漏补缺。JavaScript编程语言可以解决许多应用问题。这些算法或其变体,经常出现在真实的面试场景中。
字符串属性和方法
字符串用于表示和操作字符序列。字符串属性和方法有很多。以下是可供参考的代码示例,包括ES2020中的“matchAll”和ES2021中的“replaceAll”。
const str ="Today is a nice day!";
console.log(str.length); // 20
console.log(str[2]); // "d"
console.log(typeof str); // "string"
console.log(typeof str[2]); // "string"
console.log(typeofString(5)); //"string"
console.log(typeofnewString(str)); //"object"
console.log(str.indexOf("is")); // 6
console.log(str.indexOf("today")); // -1
console.log(str.includes("is")); // true
console.log(str.includes("IS")); // false
console.log(str.startsWith("Today")); // true
console.log(str.endsWith("day")); // false
console.log(str.split(" ")); // ["Today", "is", "a", "nice","day!"]
console.log(str.split("")); // ["T", "o", "d", "a","y", " ", "i", "s", " ","a", " ", "n", "i", "c","e", " ", "d", "a", "y","!"]
console.log(str.split("a")); // ["Tod", "y is ", " nice d","y!"]
console.log(str +1+2); // "Today is a nice day!12"
console.log(str + str); // "Today is a nice day!Today is a niceday!"
console.log(str.concat(str)); // "Today is a nice day!Today is a niceday!"
console.log(str.repeat(2)); // "Today is a nice day!Today is a nice day!"
console.log("abc"<"bcd"); // true
console.log("abc".localeCompare("bcd")); // -1
console.log("a".localeCompare("A")); // -1
console.log("a".localeCompare("A", undefined, { numeric: true })); // -1
console.log("a".localeCompare("A", undefined, { sensitivity: "accent" })); // 0
console.log("a".localeCompare("A", undefined, { sensitivity: "base" })); // 0
console.log("a".localeCompare("A!", undefined, { sensitivity: "base", ignorePunctuation: true })); // 0
console.log("abc".toLocaleUpperCase()); // "ABC"
console.log(str.padStart(25, "*")); // "*****Todayis a nice day!"
console.log(str.padEnd(22, "!")); // "Today is anice day!!!"
console.log(" middle ".trim().length); // 6
console.log(" middle ".trimStart().length); // 8
console.log(" middle ".trimEnd().length); // 9
console.log(str.slice(6, 8)); // "is"
console.log(str.slice(-4)); // "day!"
console.log(str.substring(6, 8)); // "is"
console.log(str.substring(-4)); // "Today is a nice day!"
console.log("a".charCodeAt()); // 97
console.log(String.fromCharCode(97)); // "a"
console.log(str.search(/[a-c]/)); // 3
console.log(str.match(/[a-c]/g)); // ["a", "a", "c", "a"]
console.log([...str.matchAll(/[a-c]/g)]);
// [Array(1), Array(1), Array(1), Array(1)]
// 0: ["a", index: 3, input: "Today is a nice day!",groups: undefined]
// 1: ["a", index: 9, input: "Today is a nice day!",groups: undefined]
// 2: ["c", index: 13, input: "Today is a niceday!", groups: undefined]
// 3: ["a", index: 17, input: "Today is a niceday!", groups: undefined]
console.log([..."test1test2".matchAll(/t(e)(st(d?))/g)]);
// [Array(4), Array(4)]
// 0: (4) ["test1", "e", "st1","1", index: 0, input: "test1test2", groups: undefined]
// 1: (4) ["test2", "e", "st2","2", index: 5, input: "test1test2", groups: undefined]
console.log(str.replace("a", "z")); // Todzy is anice day!
console.log(str.replace(/[a-c]/, "z")); // Todzy is anice day!
console.log(str.replace(/[a-c]/g, "z")); // Todzy is znize dzy!
console.log(str.replaceAll("a", "z")); // Todzy is znice dzy!
console.log(str.replaceAll(/[a-c]/g, "z")); // Todzy is znize dzy!
console.log(str.replaceAll(/[a-c]/, "z")); // TypeError:String.prototype.replac
映射和集合
对于字符串操作,我们需要在某处存储中间值。数组、映射和集合都是需要掌握的常用数据结构,本文主要讨论集合和映射。
集合
Set是存储所有类型的唯一值的对象。以下是供参考的代码示例,一目了然。
const set =newSet("aabbccdefghi");
console.log(set.size); //9
console.log(set.has("d")); //true
console.log(set.has("k")); //false
console.log(set.add("k")); // {"a", "b", "c", "d","e""f", "g", "h", "i","k"}
console.log(set.has("k")); //true
console.log(set.delete("d")); //true
console.log(set.has("d")); //false
console.log(set.keys()); // {"a", "b", "c","e""f", "g", "h", "i","k"}
console.log(set.values()); // {"a", "b", "c","e""f", "g", "h", "i","k"}
console.log(set.entries()); // {"a" => "a","b" => "b", "c" => "c","e" => "e",
//"f"=> "f", "g" => "g", "h" =>"h"}, "i" => "i", "k" =>"k"}
const set2 =newSet();
set.forEach(item => set2.add(item.toLocaleUpperCase()));
set.clear();
console.log(set); // {}
console.log(set2); //{"A", "B", "C", "E", "F","G", "H", "I", "K"}
console.log(newSet([{ a:1, b:2, c:3 }, { d:4, e:5 }, { d:4, e:5 }]));
// {{a:1, b:2,c:3}, {d:4, e:5}, {d:4, e:5}}
const item = { f:6, g:7 };
console.log(newSet([{ a:1, b:2, c:3 }, item, item]));
// {{a:1, b:2,c:3}, {f:6, g:7}}
映射
映射是保存键值对的对象。任何值都可以用作键或值。映射会记住键的原始插入顺序。以下是供参考的代码示例:
const map =newMap();
console.log(map.set(1, "first")); // {1 =>"first"}
console.log(map.set("a", "second")); // {1 =>"first", "a" => "second"}
console.log(map.set({ obj: "123" }, [1, 2, 3]));
// {1 => "first", "a" =>"second", {obj: "123"} => [1, 2, 3]}
console.log(map.set([2, 2, 2], newSet("abc")));
// {1 => "first", "a" => "second",{obj: "123"} => [1, 2, 3], [2, 2, 2] => {"a","b", "c"}}
console.log(map.size); // 4
console.log(map.has(1)); // true
console.log(map.get(1)); // "first"
console.log(map.get("a")); // "second"
console.log(map.get({ obj: "123" })); // undefined
console.log(map.get([2, 2, 2])); // undefined
console.log(map.delete(1)); // true
console.log(map.has(1)); // false
const arr = [3, 3];
map.set(arr, newSet("xyz"));
console.log(map.get(arr)); // {"x", "y", "z"}
console.log(map.keys()); // {"a", {obj: "123"}, [2, 2,2], [3, 3]}
console.log(map.values()); // {"second", [1, 2, 3], {"a","b", "c"}, {"x", "y", "z"}}
console.log(map.entries());
// {"a" => "second", {obj: "123"}=> [1, 2, 3], [2, 2, 2] => {"a", "b", "c"},[3, 3] => {"x", "y", "z"}}
const map2 =newMap([["a", 1], ["b", 2], ["c", 3]]);
map2.forEach((value, key, map) =>console.log(`value = ${value}, key = ${key}, map = ${map.size}`));
// value = 1, key = a, map = 3
// value = 2, key = b, map = 3
// value = 3, key = c, map = 3
map2.clear();
console.log(map2.entries()); // {}
应用题
面试中有英语应用题,我们探索了一些经常用于测试的算法。
全字母短句
全字母短句是包含字母表中所有26个字母的句子,不分大小写。理想情况下,句子越短越好。以下为全字母短句:
· Waltz, bad nymph, for quick jigs vex. (28个字母)
· Jived fox nymph grabs quick waltz. (28个字母)
· Glib jocks quiz nymph to vex dwarf. (28个字母)
· Sphinx of black quartz, judge my vow. (29个字母)
· How vexingly quick daft zebras jump! (30个字母)
· The five boxing wizards jump quickly. (31个字母)
· Jackdaws love my big sphinx of quartz. (31个字母)
· Pack my box with five dozen liquor jugs. (32个字母)
· The quick brown fox jumps over a lazy dog. (33个字母)
还有很多方法可以验证给定的字符串是否是全字母短句。这一次,我们将每个字母(转换为小写)放入映射中。如果映射大小为26,那么它就是全字母短句。
/**
* An algorithm to verify whethera given string is a pangram
* @param {string} str The string to be verified
* @return {boolean} Returns whether it is a pangram
*/
functionisPangram(str) {
constlen = str.length;
if (len <26) {
returnfalse;
}
constmap =newMap();
for (let i =0; i < len; i++) {
if (str[i].match(/[a-z]/i)) { // if it is letter a to z, ignoring the case
map.set(str[i].toLocaleLowerCase(), true); // use lower case letter as a key
}
}
returnmap.size===26;
}
以下是验证测试:
console.log(isPangram("")); // false
console.log(isPangram("Bawds jog, flick quartz, vex nymphs.")); // true
console.log(isPangram("The quick brown fox jumped over the lazy sleepingdog.")); // true
console.log(isPangram("Roses are red, violets are blue, sugar is sweet,and so are you.")); // false
同构字符串
给定两个字符串s和t,如果可以替换掉s中的字符得到t,那么这两个字符串是同构的。s中的所有字符转换都必须应用到s中相同的字符上,例如,murmur与tartar为同构字符串,如果m被t替换,u被a替换,r被自身替换。以下算法使用数组来存储转换字符,也适用于映射。
/**
* An algorithm to verify whethertwo given strings are isomorphic
* @param {string} s The first string
* @param {string} t The second string
* @return {boolean} Returns whether these two strings are isomorphic
*/
functionareIsomorphic(s, t) {
// strings with different lengths are notisomorphic
if (s.length !== t.length) {
returnfalse;
}
// the conversion array
const convert = [];
for (let i =0; i < s.length; i++) {
// if the conversioncharacter exists
if (convert[s[i]]) {
// apply the conversion and compare
if (t[i] === convert[s[i]]) { // so far so good
continue;
}
returnfalse; // not isomorphic
}
// set the conversion character for future use
convert[s[i]] = t[i];
}
// these two strings are isomorphic since there are no violations
returntrue;
};
以下是验证测试:
console.log(areIsomorphic("atlatl", "tartar")); // true
console.log(areIsomorphic("atlatlp", "tartarq")); // true
console.log(areIsomorphic("atlatlpb", "tartarqc")); // true
console.log(areIsomorphic("atlatlpa", "tartarqb")); // false
相同字母异构词
相同字母异构词是通过重新排列不同单词的字母而形成的单词,通常使用所有原始字母一次。从一个池中重新排列单词有很多种可能性。例如,cat的相同字母异构词有cat、act、atc、tca、atc和tac。我们可以添加额外的要求,即新单词必须出现在源字符串中。如果源实际上是actually,则结果数组是[“act”]。
/**
* Given a pool to compose ananagram, show all anagrams contained (continuously) in the source
* @param {string} source A source string to draw an anagram from
* @param {string} pool A pool to compose an anagram
* @return {array} Returns an array of anagrams that are contained by the source string
*/
functionshowAnagrams(source, pool) {
// if source is not long enough to hold theanagram
if (source.length< pool.length) {
return [];
}
const sourceCounts = []; // an array tohold the letter counts in source
const poolCounts = []; // an array tohold the letter counts in pool
// initialize counts for 26 letters to be 0
for (let i =0; i <26; i++) {
sourceCounts[i] =0;
poolCounts[i] =0;
}
// convert both strings to lower cases
pool = pool.toLocaleLowerCase();
const lowerSource = source.toLocaleLowerCase();
for (let i =0; i < pool.length; i++) {
// calculatepoolCounts for each letter in pool, mapping a - z to 0 - 25
poolCounts[pool[i].charCodeAt() -97]++;
}
const result = [];
for (let i =0; i < lowerSource.length; i++) {
// calculatesourceCounts for each letter for source, mapping a - z to 0 - 25
sourceCounts[lowerSource[i].charCodeAt() -97]++;
if (i >= pool.length-1) { // if source islong enough
// if sourceCountsis the same as poolCounts
if (JSON.stringify(sourceCounts) ===JSON.stringify(poolCounts)) {
// save the found anagram, using the original source to make stringcase-preserved
result.push(source.slice(i - pool.length+1, i +1));
}
// shift thestarting window by 1 index (drop the current first letter)
sourceCounts[lowerSource[i - pool.length+1].charCodeAt() -97]--;
}
}
// removeduplicates by a Set
return [...newSet(result)];
}
以下是验证测试:
console.log(showAnagrams("AaaAAaaAAaa", "aa")); // ["Aa", "aa", "aA", "AA"]
console.log(showAnagrams("CbatobaTbacBoat", "Boat")); //["bato", "atob", "toba", "obaT","Boat"]
console.log(showAnagrams("AyaKkayakkAabkk", "Kayak"));
// ["AyaKk", "yaKka", "aKkay", "Kkaya","kayak", "ayakk", "yakkA"]
回文
回文是从前往后读和从后往前读读法相同的单词或句子。有很多回文,比如A,Bob,还有 “A man, a plan, a canal — Panama”。检查回文的算法分为两种。使用循环或使用递归从两端检查是否相同。下列代码使用递归方法:
/**
* An algorithm to verify whethera given string is a palindrome
* @param {string} str The string to be verified
* @return {boolean} Returns whether it is a palindrome
*/
functionisPalindrome(str) {
functioncheckIsPalindrome(s) {
// empty stringor one letter is a defecto palindrome
if (s.length<2) {
returntrue;
}
if ( // if two ends notequal, ignoring the case
s[0].localeCompare(s[s.length-1], undefined, {
sensitivity: "base",
}) !== 0
) {
returnfalse;
}
// since two ends equal, checking the inside
returncheckIsPalindrome(s.slice(1, -1));
}
// check whether it is a palindrome, removing noneletters and digits
returncheckIsPalindrome(str.replace(/[^A-Za-z0-9]/g, ""));
}
以下是验证测试:
console.log(isPalindrome("")); // true
console.log(isPalindrome("a")); // true
console.log(isPalindrome("Aa")); // true
console.log(isPalindrome("Bob")); // true
console.log(isPalindrome("Odd or even")); // false
console.log(isPalindrome("Never odd or even")); // true
console.log(isPalindrome("02/02/2020")); // true
console.log(isPalindrome("2/20/2020")); // false
console.log(isPalindrome("A man, a plan, a canal – Panama")); // true
回文面试题有很多不同的变形题,下面是一个在给定字符串中寻找最长回文的算法。
/**
* An algorithm to find thelongest palindrome in a given string
* @param {string} source The source to find the longest palindrome from
* @return {string} Returns the longest palindrome
*/
functionfindLongestPalindrome(source) {
// convert to lower cases and only keep lettersand digits
constlettersAndDigits = source.replace(/[^A-Za-z0-9]/g, "");
const str = lettersAndDigits.toLocaleLowerCase();
const len = str.length;
// empty string or one letter is a defecto palindrome
if (len <2) {
return str;
}
// the first letter is the current longest palindrome
let maxPalindrome = lettersAndDigits[0];
// assume that the index is the middle of a palindrome
for (let i =0; i < len; i++) {
// try the case that the palindrome has one middle
for (
let j =1; // start with onestep away (inclusive)
j < len &&// end with the len end (exclusive)
i - j >= 0&&// cannot pass the start index (inclusive)
i + j < len &&// cannot exceed end index (exclusive)
Math.min(2 * i +1, 2 * (len - i) -1) > maxPalindrome.length; // potential max length should be longer than thecurrent length
j++
) {
if (str[i - j] !== str[i + j]) { // if j stepsbefore the middle is different from j steps after the middle
break;
}
if (2 * j +1> maxPalindrome.length) { // if it is longerthan the current length
maxPalindrome = lettersAndDigits.slice(i - j, i + j +1); // j steps before, middle, and j steps after
}
}
// try the case that the palindrome has two middles
if (i < len -1&& str[i] === str[i +1]) { // if two middles are the same
if (maxPalindrome.length<2) { // the string withtwo middles could be the current longest palindrome
maxPalindrome = lettersAndDigits.slice(i, i +2);
}
for (
let j =1; // start with one step away (inclusive)
j < len -1&&// end with the len - 1 end (exclusive)
i - j >= 0&&// cannot pass the start index (inclusive)
i + j +1< len &&// cannot exceed end index (exclusive)
Math.min(2 * i +2, 2 * (len - i)) > maxPalindrome.length; // potential max length should be longer than thecurrent length
j++
) {
if (str[i - j] !== str[i + j +1]) { // if j stepsbefore the left middle is different from j steps after the right middle
break;
}
if (2 * j +2> maxPalindrome.length) { // if it is longer than the current length
maxPalindrome = lettersAndDigits.slice(i - j, i + j +2); // j steps before, middles, and j steps after
}
}
}
}
return maxPalindrome;
}
以下是验证测试:
console.log(findLongestPalindrome("")); // ""
console.log(findLongestPalindrome("abc")); // "a"
console.log(findLongestPalindrome("Aabcd")); // "Aa"
console.log(findLongestPalindrome("I am Bob.")); // "Bob"
console.log(findLongestPalindrome("Odd or even")); // "Oddo"
console.log(findLongestPalindrome("Never odd or even")); // "Neveroddoreven"
console.log(findLongestPalindrome("Today is 02/02/2020.")); // "02022020"
console.log(findLongestPalindrome("It is 2/20/2020.")); // "20202"
console.log(findLongestPalindrome("A man, a plan, a canal – Panama")); // "AmanaplanacanalPanama"
"
熟能生巧。享受编码!
留言点赞关注
我们一起分享AI学习与发展的干货
如转载,请后台留言,遵守转载规范