Citrix OA求讨论

Job Hunting Interview
, , , ,
1

WeChat%20Image_20190910220451
WeChat Image_20190910220451.jpg4032×3024 4.27 MB

同学做的时候TLE了，我还没拿到，讨论一下题目。
我的做法是每个substring用hashMap判断一下Palindrome, 复杂度有点高，想问一下有人有好的解法吗？

2

自己回复自己。。用位运算可以到n^2, 再加一个HashSet可以更小一点

3

这里先说一点，参考 LC 266 Palindrome Permutation 和 https://leetcode.com/articles/palindrome-permutation/

public class Solution {
    public boolean canPermutePalindrome(String s) {
        Set < Character > set = new HashSet < > ();
        for (int i = 0; i < s.length(); i++) {
            if (!set.add(s.charAt(i)))
                set.remove(s.charAt(i));
        }
        return set.size() <= 1;
    }
}

一个set可以解决一个string，然后看下多个string的情况

4

感谢

5

n^2加hashset存之前的pali，降低一点复杂度，应该可以过了

6

对单独一个string，double for loop 可以解决。不确定是最优的。
现在题目是n个string，那么是不是要做memorization，对处理过的substring要记一下？

BTW，你那个n是啥？

7

补充一下，所有的valid的substring其实对应两种情况，一种是empty set （case A），一种是一个letter （case B）。

如果在该valid的substring上expand：
case A： 可以加一个任意letter（左边或右边），或者任意两个一样的letter（两边）
case B：可以加一个跟B一样的letter（左边或右边），或者任意两个一样的letter（两边）

这样某种意义上可以进一步优化，因为你可以在原来valid 的substring 上expand。

8

n就是input进去的字符串长度， N（N-1）/2是可能的substring数量,我觉得可以 ，用hashmap记录，可以更低一点，达不到N^2,想错了。

9

但这里不是n个string吗

10

哦哦你这个意思 那就是存一下处理过的String

11

OA就算了吧，不优化了

12

嗯 可能同学是其他问题 谢谢版主