ARTS #162

Algorithm

本周选择的算法题是：Interleaving String。

规则

Given strings s1, s2, and s3, find whether s3 is formed by an interleaving of s1 and s2.

An interleaving of two strings s and t is a configuration where they are divided into non-empty substrings such that:

s = s1 + s2 + ... + sn
t = t1 + t2 + ... + tm
|n - m| <= 1
The interleaving is s1 + t1 + s2 + t2 + s3 + t3 + ... or t1 + s1 + t2 + s2 + t3 + s3 + ...

Note: a + b is the concatenation of strings a and b.

Example 1:

Input: s1 = "aabcc", s2 = "dbbca", s3 = "aadbbcbcac"
Output: true

Example 2:

Input: s1 = "aabcc", s2 = "dbbca", s3 = "aadbbbaccc"
Output: false

Example 3:

Input: s1 = "", s2 = "", s3 = ""
Output: true

Constraints:

0 <= s1.length, s2.length <= 100
0 <= s3.length <= 200
s1, s2, and s3 consist of lowercase English letters.

Follow up: Could you solve it using only O(s2.length) additional memory space?

Solution

impl Solution {
    pub fn is_interleave(s1: String, s2: String, s3: String) -> bool {
        if s1.len() + s2.len() != s3.len() { return false; }
        
        let s1 = s1.as_bytes();
        let s2 = s2.as_bytes();
        let s3 = s3.as_bytes();

        let mut dp = vec![false; s2.len()+1];
        for i in 0..=s1.len() {
            for j in 0..=s2.len() {
                if i == 0 && j == 0 {
                    dp[j] = true;
                } else if i == 0 {
                    dp[j] = dp[j-1] && (s2[j-1] == s3[i+j-1]);
                } else if j == 0 {
                    dp[j] = dp[j] && (s1[i-1] == s3[i+j-1]);
                } else {
                    dp[j] = dp[j] && (s1[i-1] == s3[i+j-1]) || (dp[j-1] && (s2[j-1] == s3[i+j-1]));
                }
            }
        }

        dp[s2.len()]
    }
}

Review

作者手把手带你用 Rust 实现 Base64 算法，涵盖了重组、编解码、padding 等全部知识，同时学习 Rust 语法和 Base64 算法，非常划算~

Tip

本周用 Hopper 反编译了 Figma 的 Quicklook 插件，成功读取到了 Figma 的预览图：

int main(int argc, const char * argv[]) {
    @autoreleasepool {
        FILE *rax = fopen("/path/to/fig", "rb");
        FILE *r15 = rax;
        
        void *r50 = NULL;
        fread(&r50, 8, 1, rax);
        assert(fseek(r15, 0xc, 0) == 0);
        
        long var34 = 0;
        assert(fread(&var34, 4, 1, r15) == 1);
        assert(fseek(r15, var34, 1) == 0);
        
        long var30 = 0;
        assert(fread(&var30, 4, 1, r15) == 1);
        assert(fseek(r15, var30, 1) == 0);
        
        long var2c = 0;
        assert(fread(&var2c, 4, 1, r15) == 1);
        
        long r13 = var2c;
        assert(r13 != 0);
        
        void *r12 = malloc(r13);
        assert(fread(r12, r13, 1, r15) == 1);
        
        CGDataProviderRef rdi = CGDataProviderCreateWithData(0, r12, r13, 0);
        if (r13 >= 9) {
            CGImageRef image = CGImageCreateWithPNGDataProvider(rdi, 0, 0, 0);
            NSLog(@"%@", image);
        }
    }
    return 0;
}

分享一则趣事~

最近和女儿一起看火影，看到了第11集（英雄的国度）：

这一幕发生后，她控制不住的哭了，许久之后才停下，然后问了很多问题：

她：“为什么他爸爸会死“

我：”他们遇到坏人了，坏人想占领这个国家，所以就把他爸爸杀掉了“

她：“为什么坏人不杀妈妈”

我：“坏人要杀的是能为国家挺身而出的人，他妈妈不会，他爸爸会，所以坏人就杀掉了他爸爸”

她（再一次）：“为什么他爸爸会死“

我：“因为坏人太坏了，坏人还有很多帮手，他爸爸一个人打不赢他们”

她：“他的爸爸会不会复活”

我：“不会… 每个人的生命都只有一次，我们要保护好自己，过马路的时候要注意看车；在电梯里不要跳；…”

她：“那奥特曼为什么不会死呢”

我：“因为奥特曼很厉害，奥特曼还有很多兄弟，奥特曼打不赢的时候就会找兄弟来帮忙，就像他们修桥时找忍者来帮忙一样”

她：“他爸爸不厉害是吗”

我：“他爸爸没有奥特曼厉害“，感觉这个回答会把她带偏，所以我补充到：”他只是一个普通人，一个渔民而已，重要的不是他厉不厉害，而是他有勇气去面对邪恶，他也不想当英雄，但他有勇气，其他人没有，所以大家认为他是英雄。英雄也会失败，不用对他们太苛刻，反而要质问环境为何需要英雄，邪恶为何这么坏，其他人为何缺少勇气”

她：“坏人为什么要杀英雄“

我：“坏人想占领这个国家，但英雄会保护这个国家，所以坏人只能先杀掉英雄”

她：“爸爸你不要当英雄，会被坏人杀掉的”

我：“英雄是为了保护自己珍爱的人才挺身而出的，就算爸爸不当英雄，如果有人伤害你，爸爸妈妈也会保护你的”

…

这段关于英雄的探讨，最后以她的结论 “千万不要当英雄” 结束，她最近几乎逢人就说 “xx，你不要当英雄，会被坏人杀掉的”。

Algorithm

规则

Solution

Review

Tip

Share