[JAVA] DFS with memo
\'\'\'\n\n\tclass Solution {\n\t\tint MOD = (int)1e9 + 7;\n\t\tpublic int numPermsDISequence(String s) {\n\t\t\tif (s == null || s.length() == 0) {\n\t\t\t\tret
\'\'\'\n\n\tclass Solution {\n\t\tint MOD = (int)1e9 + 7;\n\t\tpublic int numPermsDISequence(String s) {\n\t\t\tif (s == null || s.length() == 0) {\n\t\t\t\treturn 0;\n\t\t\t}\n\t\t\tSet<Integer> hashSet = new HashSet<>();\n\t\t\tfor (int i = 0; i <= s.length(); i++) {\n\t\t\t\thashSet.add(i);\n\t\t\t}\n\n\t\t\tlong result = helper(s, 0, hashSet, null, null, new boolean[s.length() + 1][s.length() + 1], new long[s.length() + 1][s.length() + 1]);\n\t\t\tSystem.out.println(result);\n\t\t\treturn (int)(result % MOD);\n\t\t}\n\n\t\tpublic long helper(String s, int startIndex, Set<Integer> hashSet, Integer lastNumber, Integer relativeIndex, boolean[][] visited, long[][] dp) {\n\t\t\tif (startIndex == s.length() + 1) {\n\t\t\t\treturn 1;\n\t\t\t}\n\t\t\tif (relativeIndex != null && visited[startIndex][relativeIndex]) {\n\t\t\t\treturn dp[startIndex][relativeIndex];\n\t\t\t}\n\n\t\t\tlong result = 0;\n\t\t\tint index = -1;\n\t\t\tPriorityQueue<Integer> pQueue = new PriorityQueue<Integer>(hashSet); \n\t\t\tfor (int i : pQueue) {\n\t\t\t\tindex++;\n\t\t\t\tif (startIndex != 0 && ((s.charAt(startIndex - 1) == \'D\' && i > lastNumber) || \n\t\t\t\t\t\t\t\t\t\t(s.charAt(startIndex - 1) == \'I\' && i < lastNumber))) {\n\t\t\t\t\tcontinue;\n\t\t\t\t}\n\t\t\t\thashSet.remove(i);\n\t\t\t\tresult += helper(s, startIndex + 1, hashSet, i, index, visited, dp);\n\t\t\t\tresult %= MOD;\n\t\t\t\thashSet.add(i);\n\t\t\t}\n\n\t\t\tif (relativeIndex != null) {\n\t\t\t\tvisited[startIndex][relativeIndex] = true;\n\t\t\t\tdp[startIndex][relativeIndex] = result;\n\t\t\t}\n\t\t\treturn result;\n\t\t}\n\t}\n\'\'\'\n\n
[]