97 篇博文 含有标签「字符串」

1、题干​

如果字符串满足以下条件之一，则可以称之为 有效括号字符串（valid parentheses string，可以简写为 VPS）：

• 字符串是一个空字符串 ""，或者是一个不为 "(" 或 ")" 的单字符。
• 字符串可以写为 AB（A 与 B 字符串连接），其中 A 和 B 都是 有效括号字符串 。
• 字符串可以写为 (A)，其中 A 是一个 有效括号字符串 。

类似地，可以定义任何有效括号字符串 S 的 嵌套深度 depth(S)：

• depth("") = 0
• depth(C) = 0，其中 C 是单个字符的字符串，且该字符不是 "(" 或者 ")"
• depth(A + B) = max(depth(A), depth(B))，其中 A 和 B 都是 有效括号字符串
• depth("(" + A + ")") = 1 + depth(A)，其中 A 是一个 有效括号字符串

例如：""、"()()"、"()(()())" 都是 有效括号字符串（嵌套深度分别为 0、1、2），而 ")(" 、"(()" 都不是 有效括号字符串 。

给你一个 有效括号字符串 s，返回该字符串的 s 嵌套深度 。

示例 1：

输入：s = "(1+(2*3)+((8)/4))+1"
输出：3
解释：数字 8 在嵌套的 3 层括号中。

示例 2：

输入：s = "(1)+((2))+(((3)))"
输出：3

提示：

• 1 <= s.length <= 100
• s 由数字 0-9 和字符 '+'、'-'、'*'、'/'、'('、')' 组成
• 题目数据保证括号表达式 s 是 有效的括号表达式

2、解题思路​

根据题意统计左括号数量sum和最大值max，遇到左括号(数量sum加1并更新最大值max，遇到右括号)数量sum减1，最后返回最大值max。

3、代码​

var maxDepth = function (s) {
    let sum = 0, max = 0;
    for (const c of s) {
        if (c === '(') max = Math.max(++sum, max);
        else if (c === ')') --sum;
    }
    return max;
};

4、执行结果​

执行用时: 72 ms 内存消耗: 39 MB

5、整活​

用数组的reduce函数遍历字符串，把代码缩减成1行，空间和时间也都有所减少，突然觉得自己又行了😏。

但是，实际项目不推荐这么写，一般情况下写代码更应该重视可维护性。试想这样一行代码过两天自己都看不懂，接手的人心理活动又会是什么样😂。

6、代码​

var maxDepth = s => [].reduce.call(s, (a, c) => (c === '(' ? ++a[0] > a[1] && (a[1] = a[0]) : c === ')' && --a[0], a), [0, 0])[1];

7、执行结果​

1、题干​

给你一个字符串 path ，表示指向某一文件或目录的 Unix 风格 绝对路径 （以 '/' 开头），请你将其转化为更加简洁的规范路径。

在 Unix 风格的文件系统中，一个点（.）表示当前目录本身；此外，两个点 （..） 表示将目录切换到上一级（指向父目录）；两者都可以是复杂相对路径的组成部分。任意多个连续的斜杠（即，'//'）都被视为单个斜杠 '/' 。 对于此问题，任何其他格式的点（例如，'...'）均被视为文件/目录名称。

请注意，返回的 规范路径 必须遵循下述格式：

• 始终以斜杠 '/' 开头。
• 两个目录名之间必须只有一个斜杠 '/' 。
• 最后一个目录名（如果存在）不能 以 '/' 结尾。
• 此外，路径仅包含从根目录到目标文件或目录的路径上的目录（即，不含 '.' 或 '..'）。

返回简化后得到的 规范路径 。

示例 1：

输入：path = "/home/"
输出："/home"
解释：注意，最后一个目录名后面没有斜杠。 

示例 2：

输入：path = "/../"
输出："/"
解释：从根目录向上一级是不可行的，因为根目录是你可以到达的最高级。

示例 3：

输入：path = "/home//foo/"
输出："/home/foo"
解释：在规范路径中，多个连续斜杠需要用一个斜杠替换。

示例 4：

输入：path = "/a/./b/../../c/"
输出："/c"

提示：

• 1 <= path.length <= 3000
• path 由英文字母，数字，'.'，'/' 或 '_' 组成。
• path 是一个有效的 Unix 风格绝对路径。

2、解法1​

将path字符串按/分割为目录数组dirs，过滤dirs中的空串和.号；再遍历dirs，遇到..则出栈，反之入栈；最后使用/拼接栈中剩余目录。

3、代码​

var simplifyPath = function (path) {
    const dirs = path.split('/').filter(c => c && c !== '.');
    return '/' + dirs.reduce((acc, cur) => (cur === '..' ? acc.pop() : acc.push(cur), acc), []).join('/');
};

4、执行结果​

5、解法2​

使用Node.js内置的path模块解析路径。

6、代码​

var simplifyPath = function (p) {
    return require('path').resolve(p);
};

7、执行结果​

执行用时: 84 ms 内存消耗: 39.9 MB

1、题干​

给你一个仅包含小写英文字母和 '?' 字符的字符串 s，请你将所有的 '?' 转换为若干小写字母，使最终的字符串不包含任何 连续重复 的字符。

注意：你 不能 修改非 '?' 字符。

题目测试用例保证 除 '?' 字符 之外，不存在连续重复的字符。

在完成所有转换（可能无需转换）后返回最终的字符串。如果有多个解决方案，请返回其中任何一个。可以证明，在给定的约束条件下，答案总是存在的。

示例 1：

输入：s = "?zs"
输出："azs"
解释：该示例共有 25 种解决方案，从 "azs" 到 "yzs" 都是符合题目要求的。只有 "z" 是无效的修改，因为字符串 "zzs" 中有连续重复的两个 'z' 。

示例 2：

输入：s = "ubv?w"
输出："ubvaw"
解释：该示例共有 24 种解决方案，只有替换成 "v" 和 "w" 不符合题目要求。因为 "ubvvw" 和 "ubvww" 都包含连续重复的字符。

提示：

• 1 <= s.length <= 100

• s 仅包含小写英文字母和 '?' 字符

2、解题思路​

遍历字符串s，查找与'?'前后字符不相等的字母用于替换。其中字典dict可优化为3个字母，因为只需保证所有连续3个字符不相等，就能保证最终的字符串不包含任何连续重复的字符。

3、代码​

var modifyString = function (s) {
    const dict = ['a', 'b', 'c'];
    return [].reduce.call(s, (acc, cur, i) => {
        return acc + (cur !== '?' ? cur : dict.find(c => c !== acc[i - 1] && c !== s[i + 1]));
    }, '');;
};

4、执行结果​

1、题干​

给你一个 不含重复 单词的字符串数组 words ，请你找出并返回 words 中的所有 连接词 。

连接词 定义为：一个完全由给定数组中的至少两个较短单词（不一定是不同的两个单词）组成的字符串。

示例 1：

输入：words = ["cat","cats","catsdogcats","dog","dogcatsdog","hippopotamuses","rat","ratcatdogcat"]
输出：["catsdogcats","dogcatsdog","ratcatdogcat"]
解释："catsdogcats" 由 "cats", "dog" 和 "cats" 组成; 
     "dogcatsdog" 由 "dog", "cats" 和 "dog" 组成; 
     "ratcatdogcat" 由 "rat", "cat", "dog" 和 "cat" 组成。

示例 2：

输入：words = ["cat","dog","catdog"]
输出：["catdog"]

提示：

• 1 <= words.length <= 104
• 1 <= words[i].length <= 30
• words[i] 仅由小写英文字母组成。 
• words 中的所有字符串都是 唯一 的。
• 1 <= sum(words[i].length) <= 105

常规解法用字典树处理，详情可以看官解。 补充：这个解法有漏洞，调整用例肯定还会超时

2、解题思路​

这里采用一种非常规解法，创建哈希集合set并加入所有单词，然后遍历所有单词并判断该单词是否由set中的元素组成，判断过程是利用递归对每个单词进行分段，如果set包含所有分段后的子串则说明其是连接词。

然后写出了下面这段代码，结果通过用例43/44，最后一个用例超时。主要是因为这个用例的特殊性，导致递归检查函数的执行次数暴涨。

var findAllConcatenatedWordsInADict = function (words) {
    const set = new Set(words);
    if (set.has("")) set.delete("");

    function dfs(word, start) {
        let s = '';
        for (let i = start; i < word.length; i++) {
            s += word[i];
            if (set.has(s) && dfs(word, i + 1)) return true;
        }
        return set.has(s) && start;
    }

    return words.reduce((acc, cur) => (dfs(cur, 0) && acc.push(cur), acc), []);
};

由于该用例的特殊性，尝试添加预检策略绕过一些特殊用例：

• 1、字符串数组按长度升序排序，由于长单词肯定由短单词组成，意味着如果前面的短单词无法组合出当前单词的特征，就说明其不是连接词
• 2、预检函数，取出单词中所有连续的两个字符（最短连接子串），检查更短的单词是否包含或能组合出这个最短连接子串，如果为否则说明其不是连接词

3、完整代码​

var findAllConcatenatedWordsInADict = function (words) {
    words.sort((a, b) => a.length - b.length);
    const set = new Set(words);
    if (set.has('')) set.delete('');

    function dfs(word, start) {
        let s = '';
        for (let i = start; i < word.length; i++) {
            s += word[i];
            if (set.has(s) && dfs(word, i + 1)) return true;
        }
        return set.has(s) && start;
    }

    const headSet = new Set(), tailSet = new Set(), compSet = new Set();
    function preCheck(word) {
        let found = true, comps = [];
        for (let i = 0; i < word.length - 1; i++) {
            const s = word[i] + word[i + 1];
            if (!compSet.has(s) && !(tailSet.has(s[0]) && headSet.has(s[1]))) found = false;
            comps.push(s);
        }
        headSet.add(word[0]), tailSet.add(word[word.length - 1]);
        for (const c of comps) compSet.add(c);
        return found;
    }

    return words.reduce((acc, cur) => {
        if (!preCheck(cur)) return acc;
        if (dfs(cur, 0)) acc.push(cur);
        return acc;
    }, []);
};

4、执行结果​

1、题干​

给出第一个词 first 和第二个词 second，考虑在某些文本 text 中可能以 "first second third" 形式出现的情况，其中 second 紧随 first 出现，third 紧随 second 出现。

对于每种这样的情况，将第三个词 "third" 添加到答案中，并返回答案。

示例 1：

输入：text = "alice is a good girl she is a good student", first = "a", second = "good"
输出：["girl","student"]

示例 2：

输入：text = "we will we will rock you", first = "we", second = "will"
输出：["we","rock"]

提示：

• 1 <= text.length <= 1000
• text 由小写英文字母和空格组成
• text 中的所有单词之间都由 单个空格字符 分隔
• 1 <= first.length, second.length <= 10
• first 和 second 由小写英文字母组成

2、解题思路​

• 正则：使用正则表达式匹配满足条件的单词即可
  • 代码最少，但要注意处理好单词边界（\b）
• 拆分数组：将字符串按空格拆分为字符串数组，遍历并判断连续的两个单词是否符合条件即可
  • 逻辑简单易懂，坑比较少
• 直接遍历：以空格为标识，判断已遍历的单词数量、以及是否跟 first second相等即可
  • 代码略多，边界情况较多，容易踩坑

3、代码1 - 正则​

var findOcurrences = function (text, first, second) {
    return text.match(new RegExp(`(?<=\\b${first} ${second} )[a-z]+`, 'g')) || [];
};

4、代码2 - 拆分数组​

var findOcurrences = function (text, first, second) {
    const words = text.split(' ');
    return words.reduce((acc, cur, i) => {
        if (cur === second && words[i - 1] === first && words[i + 1]) acc.push(words[i + 1]);
        return acc;
    }, []);
};

5、代码3 - 直接遍历​

var findOcurrences = function (text, first, second) {
    let word = '', found = 0, res = [];
    for (let i = 0; i < text.length; i++) {
        if (text[i] !== ' ') {
            word += text[i];
            if (i < text.length - 1) continue;
        }
        if (found === 2) res.push(word), found = word === second && word === first ? 2 : (word === first ? 1 : 0);
        else if (found === 1) found = word === second ? 2 : (word === first ? 1 : 0);
        else if (found === 0) found = word === first ? 1 : 0;
        word = '';
    }

    return res;
};

6、执行结果​

1、题干​

给你一个字符串 s ，考虑其所有 重复子串 ：即 s 的（连续）子串，在 s 中出现 2 次或更多次。这些出现之间可能存在重叠。

返回 任意一个 可能具有最长长度的重复子串。如果 s 不含重复子串，那么答案为 "" 。

示例 1：

输入：s = "banana"
输出："ana"

示例 2：

输入：s = "abcd"
输出：""

提示：

• 2 <= s.length <= 3 * 104
• s 由小写英文字母组成

卷不动了，滑动窗口交了

2、执行结果​

3、解题思路​

使用滑动窗口处理，如果当前窗口字符串长度大于已找到的最长子串长度，且在原字符串的末尾能找到另一个窗口字符串，则当前窗口字符串可以更新为最长子串；重复该动作直至窗口闭合。

• 最长重复子串记为maxStr，窗口左右边界分别记为i和j，窗口内的字符串记为curStr
• 当窗口curStr的长度大于maxStr或者右边界j越界时，窗口左边界右移i++，并移除窗口curStr起始位置的字母
• 当窗口curStr的长度不大于maxStr且右边界j未越界时
  • 在窗口curStr末尾追加右边界之后的字母s[j]，并将窗口右边界右移j++
  • 若窗口curStr的长度大于maxStr且在字符串s尾部找到另一个curStr，则更新maxStr
• 最后返回maxStr

4、代码​

var longestDupSubstring = function (s) {
  let maxStr = '',curStr = '';
  for (let i = 0, j = 0; i < s.length; i++) {
    curStr = curStr.replace(s[i - 1], '');
    while (curStr.length <= maxStr.length && j < s.length) {
      curStr += s[j], j++;
      if (curStr.length > maxStr.length && s.lastIndexOf(curStr) > i) maxStr = curStr;
    }
  }
  return maxStr;
};

5、优化​

评论区有同学表示Java和C++用这个思路会超时，可能有几个方面原因：

• 1、可能Node.js的下限比较低（受限于语言执行效率），所以Node.js能过其他不行
• 2、字符串操作方法replace和+=，Java这里应该可以用StringBuilder优化，C++不太清楚能否优化
• 3、字符串索引方法lastIndexOf没有限制边界，最坏情况下会完整遍历原字符串，但是窗口扫过的字符串实际是不需要遍历的；改成下面这样限制查找起点能快700ms~1000ms左右

 if (curStr.length > maxStr.length && s.indexOf(curStr, i + 1) > -1) maxStr = curStr;

还可以考虑手写索引方法，另外引入哈希表做缓存避免重复遍历；尝试了下，用例64（30000个v的字符串）超时，这个时候简单的缓存策略是完全失效的。

附上优化后的完整代码，只需修改 lastIndexOf 那一行

var longestDupSubstring = function (s) {
    let maxStr = '', curStr = '';
    for (let i = 0, j = 0; i < s.length; i++) {
        curStr = curStr.replace(s[i - 1], '');
        while (curStr.length <= maxStr.length && j < s.length) {
            curStr += s[j], j++;
            if (curStr.length > maxStr.length && s.indexOf(curStr, i + 1) > -1) maxStr = curStr;
        }
    }
    return maxStr;
};

整体调整，更简洁的版本：

var longestDupSubstring = function (s) {
    let maxStr = '';
    for (let i = 0, j = 0; i < s.length; i++) {
        while (j - i <= maxStr.length && j < s.length && ++j) {
            if (j - i <= maxStr.length) continue;
            const curStr = s.slice(i, j);
            if (s.indexOf(curStr, i + 1) > -1) maxStr = curStr;
        }
    }
    return maxStr;
};

1、题干​

给定两个字符串 a 和 b，寻找重复叠加字符串 a 的最小次数，使得字符串 b 成为叠加后的字符串 a 的子串，如果不存在则返回 -1。

注意：字符串 "abc" 重复叠加 0 次是 ""，重复叠加 1 次是 "abc"，重复叠加 2 次是 "abcabc"。

示例 1：

输入：a = "abcd", b = "cdabcdab"
输出：3
解释：a 重复叠加三遍后为 "abcdabcdabcd", 此时 b 是其子串。

示例 2：

输入：a = "a", b = "aa"
输出：2

示例 3：

输入：a = "a", b = "a"
输出：1

示例 4：

输入：a = "abc", b = "wxyz"
输出：-1

提示：

• 1 <= a.length <= 104
• 1 <= b.length <= 104
• a 和 b 由小写英文字母组成

解法1：拼接再判断是否包含​

直接拼接字符串a，并判断a是否包含b，而拼接次数就是题目的解；拼接次数最少是Math.ceil(b.length / a.length)次，如果不行就再加1，再不行就说明解不存在应返回-1。

执行结果​

代码​

var repeatedStringMatch = function (a, b) {
    const count = Math.ceil(b.length / a.length);
    if (a.repeat(count).includes(b)) return count;
    if (a.repeat(count + 1).includes(b)) return count + 1;
    return -1;
};

解法2：正则替换再判断头尾​

先将字符串b中的a都替换掉并记录匹配数量count，然后再判断字符串b剩下的头和尾是否与a的头尾相同即可：

• 如果没有头和尾，说明正好需要count个a拼接
• 如果只有头或尾，说明需要count+1个a拼接
• 如果有头又有尾，说明需要count+2个a拼接
• 如果都不是，说明解不存在应返回-1

最开始用的是解法2，踩了2个坑费了不少时间。通过之后想写个正经算法，结果写出了解法1。 再之后。。。放弃了。。。做个API战士吧 😂

执行结果​

代码​

var repeatedStringMatch = function (a, b) {
    let count = 0;
    b = b.replace(new RegExp(a, 'g'), () => (count++, '$'));

    const s = ''.padEnd(count, '$');
    if (b === s) return count;
    if ((a + s).includes(b) || (s + a).includes(b)) return count + 1;
    if ((a + s + a).includes(b)) return count + 2;
    return -1;
};

1、题干​

给你一个字符串 date ，按 YYYY-MM-DD 格式表示一个 现行公元纪年法 日期。返回该日期是当年的第几天。

示例 1：

输入：date = "2019-01-09"
输出：9
解释：给定日期是2019年的第九天。

示例 2：

输入：date = "2019-02-10"
输出：41

提示：

• date.length == 10
• date[4] == date[7] == '-'，其他的 date[i] 都是数字
• date 表示的范围从 1900 年 1 月 1 日至 2019 年 12 月 31 日

解题思路​

• 计算当前时间与开年时间的差值，得到毫秒数差值
• 毫秒数差值再除以1天的毫秒总数（86400000ms），得到天数差值
• 天数差值再加1即可

例：计算date=2019-01-09是第几天

• 计算2019-01-09跟开年时间2019-01-01的天数差值
• 即(new Date('2019-01-09') - new Date('2019-01-01')) / 86400000 + 1
• 结果为 9

这种解法只是取巧，实际依赖于Date API，底层实现还是要考虑闰年等情况

代码​

var dayOfYear = function (date) {
    return (new Date(date) - new Date(date.slice(0, 5) + '01-01')) / 86400000 + 1;
};

1、题干​

给定一个 24 小时制（小时:分钟 "HH:MM"）的时间列表，找出列表中任意两个时间的最小时间差并以分钟数表示。

示例 1：

输入：timePoints = ["23:59","00:00"]
输出：1

示例 2：

输入：timePoints = ["00:00","23:59","00:00"]
输出：0

提示：

• 2 <= timePoints.length <= 2 * 104
• timePoints[i] 格式为 "HH:MM"

2、解法1-API排序​

前置处理：先排除3种特殊情况

• 鸽巢原理：timePoints.length > 1440，最小差值为0。因为分钟数最多1440种情况，如果分钟数量超过1440，则必定有重复值。
• 哈希去重：new Set(timePoints).size < timePoints.length，表示有重复值，最小差值为0。可以只用哈希去重而不用鸽巢原理，这里两个都用一是为省空间，二是为下一个限制条件提前去重。
• 相邻原理（瞎扯的）：timePoints.length > 720最小差值为1。因为分钟数最多1440种情况，如果分钟数超过一半而没有重复值，则必定有分钟数相邻。

后续步骤：把时间字符串转为分钟数，直接API排序并计算最小差值

• 将timePoints中的时间字符串HH:MM转成分钟数(0-1400)，构建出新的分钟数数组times
• 对times进行升序排序
• 在times数组末尾推入1440+times[0](最小分钟数)，使得最小时间和最大时间的差值计算常规化
• 对相邻分钟数求差值，最后返回最小差值

3、复杂度​

• 时间复杂度：$O(C)$，其中$2<=C<=720*log720$
• 空间复杂度：$O(C)$

4、代码​

var findMinDifference = function (timePoints) {
    if (timePoints.length > 1440 || new Set(timePoints).size < timePoints.length) return 0;
    if (timePoints.length > 720) return 1;

    const times = timePoints.map(p => 60 * (p[0] + p[1]) + 1 * (p[3] + p[4]));
    times.sort((a, b) => a - b).push(1440 + times[0]);

    return times.reduce((a, c, i) => i ? Math.min(a, c - times[i - 1]) : a, 1440);
};

5、执行结果​

6、解法2-计数排序​

前置处理：先排除3种特殊情况（同解法1）

• 鸽巢原理：timePoints.length > 1440，最小差值为0。因为分钟数最多1440种情况，如果分钟数量超过1440，则必定有重复值。
• 哈希去重：new Set(timePoints).size < timePoints.length，表示有重复值，最小差值为0。可以只用哈希去重而不用鸽巢原理，这里两个都用一是为省空间，二是为下一个限制条件提前去重。
• 相邻原理（瞎扯的）：timePoints.length > 720最小差值为1。因为分钟数最多1440种情况，如果分钟数超过一半而没有重复值，则必定有分钟数相邻。

后续步骤：把时间字符串转为分钟数，使用计数排序并计算最小差值

• 创建以分钟数为下标的数组 times，将 timePoints 中的时间字符串HH:MM转成分钟数，对 times 中的分钟数进行计数
• 对相邻分钟数求差值，计算出最小差值 minDiff
• 计算最小时间和最大时间的差值，并与上一步的最小值比较，最终结果是：Math.min(minDiff, 1440 + minTime - maxTime);

7、复杂度​

• 时间复杂度：$O(C)$，其中$C=1440$
• 空间复杂度：$O(C)$

8、代码​

var findMinDifference = function (timePoints) {
    if (timePoints.length > 1440 || new Set(timePoints).size < timePoints.length) return 0;
    if (timePoints.length > 720) return 1;

    const times = new Array(1440).fill(0);
    for (const p of timePoints) {
        times[60 * (p[0] + p[1]) + 1 * (p[3] + p[4])] += 1;
    }

    let minDiff = 1440, prev = -1440, minTime;
    for (let i = 0; i < times.length; i++) {
        if (minTime === undefined && times[i]) minTime = i;
        if (times[i]) minDiff = Math.min(minDiff, i - prev), prev = i;
    }

    return Math.min(minDiff, 1440 + minTime - prev);
};

9、执行结果​

1、题干​

某种外星语也使用英文小写字母，但可能顺序 order 不同。字母表的顺序（order）是一些小写字母的排列。

给定一组用外星语书写的单词 words，以及其字母表的顺序 order，只有当给定的单词在这种外星语中按字典序排列时，返回 true；否则，返回 false。

示例 1：

输入：words = ["hello","leetcode"], order = "hlabcdefgijkmnopqrstuvwxyz"
输出：true
解释：在该语言的字母表中，'h' 位于 'l' 之前，所以单词序列是按字典序排列的。

示例 2：

输入：words = ["word","world","row"], order = "worldabcefghijkmnpqstuvxyz"
输出：false
解释：在该语言的字母表中，'d' 位于 'l' 之后，那么 words[0] > words[1]，因此单词序列不是按字典序排列的。

示例 3：

输入：words = ["apple","app"], order = "abcdefghijklmnopqrstuvwxyz"
输出：false
解释：当前三个字符 "app" 匹配时，第二个字符串相对短一些，然后根据词典编纂规则 "apple" > "app"，因为 'l' > '∅'，其中 '∅' 是空白字符，定义为比任何其他字符都小（更多信息）。

提示：

• 1 <= words.length <= 100
• 1 <= words[i].length <= 20
• order.length == 26
• 在 words[i] 和 order 中的所有字符都是英文小写字母。

解题思路​

思路 将words中的所有字符替换为正常字典序的字符，然后使用比较运算符（大于号、小于号等）去比较所有words即可。

例子 words = ["hl","la"], order = "hlabcdefgijkmnopqrstuvwxyz"

• 将words中的字符替换为正常字典序的字符，结果为：words = ["ab","bc"]
• 使用比较运算符比较所有words，"ab"<"bc"结果为true，最终返回true

步骤

• 创建哈希映射map，遍历order，获得外星字典序（键）与正常字典序（值）的映射
• 遍历words中的所有字符串
  • 将words[i]中的字符替换为正常字典序的字符
  • 使用比较运算符比较words[i]与words[i - 1]的大小
  • 如果i && words[i] < words[i - 1]则不符合外星字典序直接返回false
• 函数运行到结尾，则说明符合外星字典序，返回true

代码​

var isAlienSorted = function (words, order) {
    const map = new Map();
    for (let i = 0; i < order.length; i++) map.set(order[i], String.fromCharCode(97 + i));

    for (let i = 0; i < words.length; i++) {
        words[i] = [...words[i]].reduce((a, c) => a + map.get(c), '');
        if (i && words[i] < words[i - 1]) return false;
    }

    return true;
};