CodingTour —

ARTS #88

Algorithm

本周选择的算法题是：Substring with Concatenation of All Words。

规则

You are given a string s and an array of strings words of the same length. Return all starting indices of substring(s) in s that is a concatenation of each word in words exactly once, in any order, and without any intervening characters.

You can return the answer in any order.

Example 1:

Input: s = "barfoothefoobarman", words = ["foo","bar"]
Output: [0,9]
Explanation: Substrings starting at index 0 and 9 are "barfoo" and "foobar" respectively.
The output order does not matter, returning [9,0] is fine too.

Example 2:

Input: s = "wordgoodgoodgoodbestword", words = ["word","good","best","word"]
Output: []

Example 3:

Input: s = "barfoofoobarthefoobarman", words = ["bar","foo","the"]
Output: [6,9,12]

Constraints:

• 1 <= s.length <= 104
• s consists of lower-case English letters.
• 1 <= words.length <= 5000
• 1 <= words[i].length <= 30
• words[i] consists of lower-case English letters.

Solution

class Solution:
    def findSubstring(self, s: str, words: List[str]) -> List[int]:
        n, m = len(words), len(words[0])
        ans, window = [], n * m
        counts = Counter(words)

        for i in range(len(s) - window + 1):
            j, seen = 0, defaultdict(int)
            while j < n:
                word = s[i+j*m:i+j*m+m]
                if word in counts and counts[word] > seen[word]:
                    seen[word] += 1
                    j += 1
                else:
                    break
            if j == n: ans.append(i)
        return ans

基于窗口的优化版，最大程度的减少循环次数：

class Solution:
    def findSubstring(self, s: str, words: List[str]) -> List[int]:
        n, m = len(words), len(words[0])
        ans, window = [], n * m
        counts = Counter(words)

        for k in range(m):
            i = k
            while i < len(s) - window + 1:
                j, seen = 0, defaultdict(int)
                while j < n:
                    word = s[i+window-(j+1)*m:i+window-j*m]
                    if word in counts and counts[word] > seen[word]:
                        seen[word] += 1
                        j += 1
                    else:
                        break
                if j == n: ans.append(i)
                i += max(n - j, 1) * m
                
        return ans

Review

All Loops Are a Code Smell

“所有的循环都是有坏味道的代码“。

这篇文章很激进，争议很大，总得来说：

• 函数式虽然看起来很爽，但是不像 while/for 可以跳出循环
• 需要关注执行性能
• 需要特殊的方式处理异步

Tip

通过 shell 脚本修改 Xcode 工程的 MARKETING_VERSION：

sed -i '' -e 's/MARKETING_VERSION \= [^\;]*\;/MARKETING_VERSION = {version};/' {pbxproj_path}

Share

对 Jekyll 生成的 HTML 进行压缩的方法。

1. 从这个链接下载 compress.html

2. 将它放到 _layout 目录下

3. 更新 default.html 的 Front Matter：

   ---
   layout: compress
   ---
   

4. 在 _config.yml 里做一些移除各种 whitespace 的配置：

   compress_html:
     clippings: all
     comments: all
     endings: all
     blanklines: false
     profile: false
     ignore:
       envs: []
   

   详细的配置见：Compress HTML in Jekyll

以博客性能优化这篇为例，HTML 还能减少 15% 左右。

注意：需要把被 include 文件里的行注释改为块注释。

如果想手动为 JS 文件优化，可以使用 Google 提供的工具。