2573.找出对应-lcp-矩阵的字符串

lcp[i][j] > 0, 说明有重复, 按照这个关系, 填完word, 最后验证由这个word得到的lcp矩阵是不是一致的

class Solution {
    /**
     * lcp[i][j] > 0, 说明有重复, 按照这个关系, 填完word,
     * 最后验证由这个word得到的lcp矩阵是不是一致的
     */
    public String findTheString(int[][] lcp) {
        int len = lcp.length;
        char[] ans = new char[len];
        Arrays.fill(ans, '0');
        char ch = 'a';
        // 检查是不是对称的矩阵, 并且右斜线是单调递减
        for (int i = 0; i < len; i++) {
            if (lcp[i][i] != len - i) {
                return "";
            }
            for (int j = i; j < len; j++) {
                if (lcp[i][j] != lcp[j][i]) {
                    return "";
                }
                // 说明第j个字符和第i个字符相等, 并且这个字符没有被赋值过
                if (lcp[i][j] != 0 && ans[j] == '0') {
                    if (ch > 'z') {
                        return "";
                    }
                    ans[j] = ch;
                }
            }
            // 如果这个领头元素是独特元素, 则使用字典序的下一个字符
            if (ans[i] == ch) {
                ch++;
            }
        }

        // 验证生成答案是不是正确的, 这里可以使用DP
        for (int i = len-1; i >= 0; i--) {
            for (int j = len-1; j >= 0; j--) {
                int actualLcp = ans[i] != ans[j]
                                ? 0
                                : ((i == len-1 || j == len-1) ? 1 : lcp[i+1][j+1]+1);
                if (lcp[i][j] != actualLcp) {
                    return "";
                }
            }
        }
        return new String(ans);
    }
}