狗家onsite

Crazy_fight 发表于 2018-8-3 03:22
不太一样
205那个cb -》 aa 是return false的我记得
但是这题是返回true

那就BFS/DFS呗

scarletthln 发表于 2018-8-2 17:39
**** 本内容被作者隐藏 ****

补充内容 (2018-8-2 17:49):

我觉得最后一题好像跟205不大一样，不知道是不是我理解有问题。这里是一步步转的。205有些valid的case这里是不行的。一个例子是aabb...zz每个字母各26个。转成zzaabb...yy（扩展成256种字符每种两个同理）。在这个里面做不到。因为无论第一步转哪个字母都会把一个字母从2-》4。这题好像只能bfs/dfs.

xsgs111 发表于 2018-8-3 04:03
我觉得最后一题好像跟205不大一样，不知道是不是我理解有问题。这里是一步步转的。205有些valid的case这 ...

public boolean mapping(String start, String end) {
        if (start == null || end == null || start.length() != end.length()) {
                return false;
        }
        Map<Character, Set<Integer>> posMap = new HashMap<>();
        for (int i = 0; i < start.length(); ++i) {
                posMap.computeIfAbsent(start.charAt(i), s -> new HashSet<>()).add(i);
        }
        // e.g. start:[ababb], end[xzyzz]
        // record all same characters positions: a -> [0,2], b -> [1,3,4]
        // for all postions group, check in end string
        for (Set<Integer> positions : posMap.values()) {
                char captain = end.charAt(positions.iterator().next());
                for (Integer pos : positions) {
                        if (end.charAt(pos) != captain) {
                                return false;
                        }
                }
        }
        return true;
}
Time & Space: O(length of start/end string)
Hope helps

scarletthln 发表于 2018-8-3 04:32
public boolean mapping(String start, String end) {
        if (start == null || end == null || start.len ...

代码侏罗纪没错，就是少考虑了corner case

Crazy_fight 发表于 2018-8-3 04:57
代码侏罗纪没错，就是少考虑了corner case

还有啥corner case。。

第五题是LC上药而旗的原题吧

Crazy_fight 发表于 2018-8-3 03:22
不太一样
205那个cb -》 aa 是return false的我记得
但是这题是返回true

那不就是只要没有1对多就都能？

scarletthln 发表于 2018-8-3 04:32
public boolean mapping(String start, String end) {
        if (start == null || end == null || start.len ...

lz提到的那个case要特殊handle.我不是特别确定这种方法要怎么handle那个case?

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

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

xsgs111 发表于 2018-8-3 08:14
lz提到的那个case要特殊handle.我不是特别确定这种方法要怎么handle那个case?
**** 本内容被作者隐藏 ** ...

这个不是应该clarification做的么。。可以先把某个character先变成special sign的吧。。

xsgs111 发表于 2018-8-3 08:14
lz提到的那个case要特殊handle.我不是特别确定这种方法要怎么handle那个case?
**** 本内容被作者隐藏 ** ...

这个case可以检查一遍end string，如果长度是26并且没有重复的