https://www.codingame.com/ide/puzzle/someones-acting-sus----
Input
6
ABCDEF
5 3
ABC
AFE
CDC
DBC
AAA
Output
NOT SUS
NOT SUS
NOT SUS
SUS
NOT SUS
https://www.codingame.com/ide/puzzle/someones-acting-sus----
Input
6
ABCDEF
5 3
ABC
AFE
CDC
DBC
AAA
Output
NOT SUS
NOT SUS
NOT SUS
SUS
NOT SUS
import java.util.*; | |
import java.io.*; | |
import java.math.*; | |
class Solution { | |
static class Graph { | |
Map<Character, Set<Character>> nodes; | |
public Graph() { | |
nodes = new HashMap<>(); | |
} | |
public void addNode(Character node) { | |
nodes.put(node, new HashSet<>()); | |
} | |
public Set<Character> get(Character node) { | |
return nodes.get(node); | |
} | |
public void connect(Character from, Character to) { | |
nodes.computeIfAbsent(from, t -> new HashSet<>()).add(to); | |
nodes.computeIfAbsent(to, t -> new HashSet<>()).add(from); | |
} | |
} | |
public static void main(String args[]) { | |
Scanner in = new Scanner(System.in); | |
int L = in.nextInt(); | |
if (in.hasNextLine()) { | |
in.nextLine(); | |
} | |
String F = in.nextLine(); | |
int N = in.nextInt(); | |
int K = in.nextInt(); | |
if (in.hasNextLine()) { | |
in.nextLine(); | |
} | |
Graph g = new Graph(); | |
for (int i = 0; i < F.length(); i++) { | |
g.addNode(F.charAt(i)); | |
} | |
// add edges | |
for (int i = 1; i < F.length() - 1; i++) { | |
g.connect(F.charAt(i), F.charAt(i)); // self loop | |
g.connect(F.charAt(i - 1), F.charAt(i)); | |
g.connect(F.charAt(i), F.charAt(i + 1)); | |
} | |
// connect first and last node to each other | |
g.connect(F.charAt(0), F.charAt(F.length() - 1)); | |
g.connect(F.charAt(0), F.charAt(0)); | |
g.connect(F.charAt(F.length() - 1), F.charAt(F.length() - 1)); | |
for (int i = 0; i < N; i++) { | |
String crewmate = in.nextLine(); | |
char startChar = crewmate.charAt(0); | |
if (startChar == '#') { | |
boolean isSus = true; | |
for (int j = 1; j < F.length(); j++) { | |
if (!isSus(crewmate, g, g.get(F.charAt(j)), 1)) { | |
isSus = false; | |
break; | |
} | |
} | |
System.out.println(isSus ? "SUS" : "NOT SUS"); | |
} else { | |
System.out.println(isSus(crewmate, g, g.get(crewmate.charAt(0)), 1) ? "SUS" : "NOT SUS"); | |
} | |
} | |
} | |
public static boolean isSus(String crewmatePath, Graph g, Set<Character> set, int index) { | |
if (index == crewmatePath.length()) { | |
return false; | |
} | |
char curr = crewmatePath.charAt(index); | |
if (curr == '#') { | |
// traverse all nodes in set | |
for (Character c : set) { | |
if (!isSus(crewmatePath, g, g.get(c), index + 1)) { | |
return false; | |
} | |
} | |
return true; | |
} else { | |
// if prev char does not connect to curr char | |
if (!set.contains(curr)) { | |
return true; | |
} else { | |
return isSus(crewmatePath, g, g.get(curr), index + 1); | |
} | |
} | |
} | |
} |