擅长:python、mysql、java
<p>递归背后的基本思想是函数做两件不同的事情:</p>
<ol>
<li>如果答案真的很简单,它会返回答案。(这是一个“基本情况”。)</li>
<li>否则,它会找出一种使问题更容易的方法,并要求自己解决问题的更简单版本。(函数调用本身就是所谓的“递归”。)</li>
</ol>
<p>对于此问题,您有两种基本情况:</p>
<ol>
<li>如果第一个字符串为空,则它是<em>anything</em>的子序列,因此是<code>True</code></李>
<li>如果第二个字符串是空的(而第一个字符串不是空的),<em>nothing</em>可以是它的子序列,因此<code>False</code></李>
</ol>
<p>然后,有两种方法可以使问题变得更容易(即,使一个或两个字符串变小):</p>
<ol>
<li>如果第一个字符匹配,则答案与在两个字符串上调用减去第一个字母的函数相同。(也就是说,<code>ac</code>是<code>artic</code>的子序列<code>c</code>是<code>rtic</code>的子序列。)</li>
<li>如果不是,则答案与使用相同的第一个字符串相同,但减去第二个字符串的第一个字母(即,<code>hac</code>是<code>cathartic</code>的子序列,<code>hac</code>是<code>athartic</code>的子序列。)</li>
</ol>
<pre><code>>>> def is_subsequence(needle: str, haystack: str) -> bool:
... if not needle:
... return True
... if not haystack:
... return False
... if needle[0] == haystack[0]:
... return is_subsequence(needle[1:], haystack[1:])
... return is_subsequence(needle, haystack[1:])
...
>>> is_subsequence("hac", "cathartic")
True
>>> is_subsequence("bat", "table")
False
</code></pre>