擅长:python、mysql、java
<p>这个问题有一个O(n)的解决方案。首先要注意的是,如果子串包含的数字是偶数或最多有一个奇数,则子串就是任何回文的变音图。e、 g.“20020”是plaindrome的换位符,因为“2”的数目是偶数,“0”的数目是奇数(最多是一个奇数),而“200202”是不正常的。在</p>
<p>所以我们只需要保持位数的奇偶性,而不是它们的和。我们可以用一个10位数字来表示所有数字的平价。从0开始,每次访问字符串中的一个数字,我们可以用(2^位)对奇偶校验数进行异或运算。下面是“02002”的示例,通过迭代二进制格式的字符串生成奇偶校验数:</p>
<pre><code>parity_array = {0000000000, 0000000001, 0000000101, 0000000100, 0000000101 0000000001}
</code></pre>
<p>现在我们需要计算线性时间内的字谜数。在奇偶校验数组上迭代时,我们使用另一个1024大小的数组(我们称之为memo)来保持奇偶校验数组中特定数字的访问次数。正如我前面提到的,当且仅当二进制奇偶校验表示中的1位的数目最多为1时,子串是可以的。因此,对于奇偶校验数组的每个成员,我们需要检查并在memo中添加11个元素,当前奇偶校验数组的值等于:{0、1、2、4或8。。。或1024}并总结结果。
总复杂度为O(n)。在</p>
<p><strong>编辑:</strong>
我为上面所解释的添加了C++代码。如果您需要,我还可以添加python代码:</p>
^{pr2}$