讨论/题目交流/1153. 字符串转化 在提交过程中有一个测试用例过不了/
1153. 字符串转化 在提交过程中有一个测试用例过不了

题目链接
https://leetcode-cn.com/contest/biweekly-contest-6/problems/string-transforms-into-another-string/

下面这个测试用例过不了

输入
"abcdefghijklmnopqrstuvwxyz"  
"bcdefghijklmnopqrstuvwxyzq"  
输出  
true  

我自己线下测试和线上自定义测试用例,输出结果都是 true,但提交验证过程就过不了,结果始终为 false,即使在代码里面添加 if 判定,当输入为上面的两个字符串时,直接返回 true,这样同样过不了这个测试用例,所以我在想提交验证系统是不是有 bug
我用 Java 和 javascript 都测试了一下,都存在这个问题

我的代码如下

class Solution {

    public boolean canConvert(String str1, String str2) {
        int len = str1.length();
        if (len != str2.length()) {
            return false;
        }
        if (len <= 1) {
            return true;
        }

        char[] chars1 = str1.toCharArray();
        char[] chars2 = str2.toCharArray();

        // 迁移表
        char[] table = new char['z' + 1];
        // 第一次更新为上游字母,发现第二个上游字母后,将值更新为 1,用于后面用来判定环上是否存在上游侧链
        char[] upperReaches = new char['z' + 1];
        // 下面 visited 用于辅助计算空闲字母数量
        boolean[] visited = new boolean['z' + 1];
        int freeCharNum = 26;
        for (int i = 0; i < len; i++) {
            char char1 = chars1[i];
            char char2 = chars2[i];

            if (!visited[char1]) {
                visited[char1] = true;
                freeCharNum--;
            }
            if (!visited[char2]) {
                visited[char2] = true;
                freeCharNum--;
            }

            if (table[char1] != 0 && table[char1] != char2) {
                // 该字母下游分叉,不可转换
                return false;
            }
            else {
                // 更新 char2 的上游字母情况
                char upperReach = upperReaches[char2];
                if (upperReach == 0) {
                    upperReaches[char2] = char1;
                }
                else if (upperReach >= 'a' && upperReach != char1) {
                    // 有上游侧链
                    upperReaches[char2] = 1;
                }
                table[char1] = char2;
            }
        }

        // 检查是否存在环
        // 下面 visited 用于辅助记录哪些字母是访问过的
        Arrays.fill(visited, false);
        for (char i = 'a'; i <= 'z'; i++) {
            if (visited[i]) {
                continue;
            }
            // 检测环的过程中记录是否有上游侧链
            boolean hasUpperSideLine = false;
            boolean hasCircle = false;
            char nextC = i;
            // 检查是否有环
            while ((nextC = table[nextC]) != 0) {
                if (visited[nextC]) {
                    // 已检查过的节点,认为可以走通转换流程
                    break;
                }

                if (upperReaches[nextC] == 1)  {
                    hasUpperSideLine = true;
                }

                if (nextC == i) {
                    // 有环
                    hasCircle = true;
                    break;
                }

                visited[nextC] = true;
            }
            visited[i] = true;

            if (hasCircle) {
                // 有环
                if (hasUpperSideLine || freeCharNum > 0) {
                    // 存在上游侧链 或 有空闲字母,可以转换
                }
                else {
                    return false;
                }
            }
        }

        return true;
    }

}
展开讨论
xiyuan-fengyu发起于 2019-08-19
最近编辑于 2019-08-20

我刚试了一下,这个问题已经修复了,楼主稍后可以再尝试下。

2
展开全部 2 讨论