图源：unsplash
字符串是一系列字符，由常数或变量构成。它是编程语言中必不可少的数据类型。本文中将重点关注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'
映射和集合
对于字符串操作，我们需要在某处存储中间值。数组、映射和集合都是需要掌握的常用数据结构，本文主要讨论集合和映射。
集合
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()); // {}
应用题
面试中有英语应用题，我们探索了一些经常用于测试的算法。
等值线
等值线图是指所含字母均只出现一次的单词。
· dermatoglyphics (15个字母)
· hydropneumatics (15个字母)
· misconjugatedly (15个字母)
· uncopyrightable (15个字母)
· uncopyrightables (16个字母)
· subdermatoglyphic (17个字母)
如何写一个算法来检测字符串是否是等值线图？有很多方法可以实现。可以把字符串放在集合中，然后自动拆分成字符。由于集合是存储唯一值的对象，如果它是一个等值线图，它的大小应该与字符串长度相同。
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()); // {}
以下是验证测试:
/** * An algorithm to verify whethera given string is an isogram * @param {string} str The string to be verified * @return {boolean} Returns whether it is an isogram */ functionisIsogram(str) { if (!str) { returnfalse; } const set =newSet(str); return set.size=== str.length; }
全字母短句
全字母短句是包含字母表中所有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，那么它就是全字母短句。
console.log(isIsogram('')); // false console.log(isIsogram('a')); // true console.log(isIsogram('misconjugatedly')); // true console.log(isIsogram('misconjugatledly')); // false
以下是验证测试:
/** * 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) { const len = str.length; if (len
同构字符串
给定两个字符串s和t，如果可以替换掉s中的字符得到t，那么这两个字符串是同构的。s中的所有字符转换都必须应用到s中相同的字符上，例如，murmur与tartar为同构字符串，如果m被t替换，u被a替换，r被自身替换。以下算法使用数组来存储转换字符，也适用于映射。
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
以下是验证测试:
/** * 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
相同字母异构词
相同字母异构词是通过重新排列不同单词的字母而形成的单词，通常使用所有原始字母一次。从一个池中重新排列单词有很多种可能性。例如，cat的相同字母异构词有cat、act、atc、tca、atc和tac。我们可以添加额外的要求，即新单词必须出现在源字符串中。如果源实际上是actually，则结果数组是[“act”]。
areIsomorphic('atlatl', 'tartar')); // true console.log(areIsomorphic('atlatlp', 'tartarq')); // true console.log(areIsomorphic('atlatlpb', 'tartarqc')); // true console.log(areIsomorphic('atlatlpa', 'tartarqb')); // false
以下是验证测试:
/** * 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-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)]; }
回文
回文是从前往后读和从后往前读读法相同的单词或句子。有很多回文，比如A，Bob，还有 “A man, a plan, a canal — Panama”。检查回文的算法分为两种。使用循环或使用递归从两端检查是否相同。下列代码使用递归方法：
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"]
以下是验证测试:
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 = 0&&// cannot pass the start index (inclusive) i + j 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 = 0&&// cannot pass the start index (inclusive) i + j +1 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"
熟能生巧。享受编码！
