介紹

總而言之是時(shí)候利用暑假鍛煉一下算法技術(shù)，一提算法面試就面露難色的情形總不能一直持續(xù)下去。本欄目面向有一定基礎(chǔ)的編程愛好者，每天（如果up不鴿）分享并解析一道LeetCode中高難度題目（通常是hard）。有興趣的小伙伴可以一起跟著做并且討論解法。目前的教材是花花醬的Leetcode Problem List【1】.

適合人群：

有一定算法基礎(chǔ)，但是還未能順利通過筆試/面試，總覺得算法題目想不明白的你。

不適合人群：

算法入門級(jí)選手（一上來就做難題可能并不合適，建議首先專注簡單/中等題目）

非常不適合人群：

算法競賽選手（這種小兒科的問題完全是在浪費(fèi)您的時(shí)間）

過往題目在這里！

不同的子序列

題目看這里，leetcode第一百一十五題，hard難度：
https://leetcode.com/problems/distinct-subsequences/

強(qiáng)烈建議讀者自己先做（不過真的會(huì)有讀者嗎，笑），有任何問題歡迎在評論區(qū)討論，up看到了會(huì)及時(shí)回復(fù)。做完了歡迎在評論區(qū)打卡～

解析

我們正在比較字符串s和t的各個(gè)字母。如果我們正在考慮的兩個(gè)字母相同，那么我們有兩種選擇：

1. 我們可以選擇匹配這兩個(gè)字母。看看如果我們移除當(dāng)前匹配的字母，剩下的子串中有多少種方式可以形成相等的子序列。

2. 我們也可以選擇跳過s中的這個(gè)字母，只使用s前面的部分繼續(xù)與t匹配。

但如果我們正在考慮的兩個(gè)字母不相同，那么我們沒有選擇，我們只能跳過s中的這個(gè)字母，繼續(xù)用s前面的部分去與t匹配。

思考樂園

上面的解釋說：“我們也可以選擇跳過s中的這個(gè)字母，只使用s前面的部分繼續(xù)與t匹配”。那么為什么我們不能選擇跳過t的這個(gè)字母，使用t前面的部分與s匹配呢？歡迎把答案寫在評論區(qū)。

今天也同樣送給大家一首好聽的歌曲，那就是，來自MC石頭的——情債！

教材鏈接

【1】https://zxi.mytechroad.com/blog/leetcode-problem-categories/