讨论/题目交流/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

通过后的代码

    /**
     * 解题思路
     * 字母的转换一共有一下几种特殊情况
     * 1. 转换前后字符串完全相等,可以转换
     * 2. 下游分叉的一定不能转换
     *  例如:a->b, a->c
     * 3. 有空闲字母的一定可以转换
     *  没有上游的字母就视为空闲字母,因为没有上游的字母可能没在转换链中出现,也可能在无环链末端(a->b->c->d,a空闲) 也可能在环链的上游侧链末端(a->b->c->d->a,f->e->a,f空闲),后面两种经过转换后,末端的字母就会空闲出来
     *  单独把1这种情况提出来,是因为 abcdefghijklmnopqrstuvwxyz -> abcdefghijklmnopqrstuvwxyz 这种情况所有字母的本身即为上游,没有空闲字母,所以要单独放在第一种情况来处理
     */
    class Solution {

        public boolean canConvert(String str1, String str2) {
            int len = str1.length();
            if (len <= 1 || str1.equals(str2)) {
                // 两个字符串完全相等时,会影响后面上游字母的判定,所以先在这里判断了
                return true;
            }

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

            // 记录下游情况,下游分叉则不可转换
            char[] lowerReaches = new char['z' + 1];
            // 记录上游情况,用来标记空闲字母,如果一个字母没有上游,则算作空闲字母(初始状态就是空闲的,或者经过一定步骤转换后可以变为空闲状态)
            // 如果有空闲字母,且不存在下游分叉的情况,一定可以转换
            char[] upperReaches = new char['z' + 1];
            int freeCharNum = 26;
            for (int i = 0; i < len; i++) {
                char char1 = chars1[i];
                char char2 = chars2[i];

                if (lowerReaches[char1] != 0 && lowerReaches[char1] != char2) {
                    // 该字母下游分叉,不可转换
                    return false;
                }
                else {
                    // 更新 char2 的上游字母情况
                    char upperReach = upperReaches[char2];
                    if (upperReach == 0) {
                        if (--freeCharNum == 0) {
                            return false;
                        }
                        upperReaches[char2] = char1;
                    }
                    // 更新 char2 的下游字母情况
                    lowerReaches[char1] = char2;
                }
            }
            return true;
        }

    }
展开全部 2 讨论