谷家电面

您好！
本帖隐藏的内容需要积分高于 155 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 155 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

补充内容 (2018-12-24 08:20):
说掉了两句，先把所有的B的substring找出来存在hashset里，然后再用backtracking遍历所有的A的substring看是不是在这个set里，在所有情况里把substring数最小的那个情况记录下来就行合起来是O(N^2+M^2)

补充内容 (2018-12-25 14:47):
经底下的提醒貌似可以直接用贪心的方法做，直接找A的最长prefix that is a substring of B，理由是不管i位的字符放在前面还是后面都不影响总的substring的个数

补充内容 (2018-12-25 14:48):
另外这还有个变体，用B的subsequence，https://www.1point3acres.com/bbs ... read&tid=460956

hzhu07 发表于 2018-12-24 01:46
总觉得在哪里见过这题，但是翻了lc似乎没有，有大神提示一下题号么

陆爸陆，应该是这题，substring的

pengbomuzzy 发表于 2018-12-25 13:05
https://www.1point3acres.com/bbs/forum.php?mod=viewthread&tid=460956&extra=&page=1  这个题，说是可 ...

对，是的
那应该就是变种

是不是我想简单了。。。类似word break O(T*T*M)  T = len(t), T = len(subs)

       public int canFormII(String t, String subs) {

                int[] memo = new int[t.length() + 1];

                Arrays.fill(memo, Integer.MAX_VALUE);

                memo[0] = 0;

                for (int i = 1; i <= t.length(); i++) {

                        for (int j = i - 1; j >=0; j--) {

                                if (subs.contains(t.substring(j, i))) {

                                        memo[i] = Math.min(memo[i], memo[j] + 1);

                                }

                        }

                        if (memo[i] == Integer.MAX_VALUE)

                                return -1;

                }

               

                return memo[t.length()] == Integer.MAX_VALUE ? -1 : memo[t.length()];

        }

总觉得在哪里见过这题，但是翻了lc似乎没有，有大神提示一下题号么

感谢楼主分享！字数字数！

难道不是dp吗。。。

sdyy1991 发表于 2018-12-24 07:37
难道不是dp吗。。。

这题貌似不可能DP 吧？

sdyy1991 发表于 2018-12-24 07:37
难道不是dp吗。。。

我开始也想用dp但是想了五分钟感觉dp不了，因为B里任意substring都可以，这个顺序没办法
想来想去只能backtracking，最后也过了所以应该没问题

补充内容 (2018-12-24 08:23):
如果能dp还望赐教

补充内容 (2018-12-24 08:25):
而且dp的复杂度应该也差不多吧，感觉经验上能backtracking加memorization的题和dp至少时间复杂度上应该是差不多的

能不能直接贪心做？ 从A的第一个字符开始找一个最长的存在B中的子字符（假设长的为len), 然后从len位置开始继续找下一个最长存在B中的的子字符串，依次类推。。。

fqbrighter 发表于 2018-12-24 09:04
能不能直接贪心做？ 从A的第一个字符开始找一个最长的存在B中的子字符（假设长的为len), 然后从len位置开始 ...

时间有点久不记得了，印象中当时找到一个反例来着
不过刚才自己画了半天好像这样也没啥问题

1. def combineSubstr(a, b):
   
2.     s = set()
   
3.     for i in range(len(b)):
   
4.         for j in range(i, len(b)):
   
5.             s.add(b[i:j+1])
   
6.     m = {}
   
7.     return findMinimumCombine(a, s, m)
   
8. 
   
9. def findMinimumCombine(a, s, m):
   
10.     if a in s:
    
11.         return 1
    
12.     if a in m:
    
13.         return m[a]
    
14.    
    
15.     res = 10**9
    
16.     for i in range(1, len(a)):
    
17.         cur = findMinimumCombine(a[:i], s, m) + findMinimumCombine(a[i:], s, m)
    
18.         res = min(res, cur)
    
19. 
    
20.     m[a] = res
    
21.     return res

复制代码

请问楼主, 大概是这样写吗? 是不是对a的每一个子字符串再进行分割, 同时用memorization节省时间? 谢谢~