Skip to content

Instantly share code, notes, and snippets.

@ahmedash95
Last active December 12, 2021 01:46
Show Gist options
  • Save ahmedash95/53edfe726670a3aa03896033061cc873 to your computer and use it in GitHub Desktop.
Save ahmedash95/53edfe726670a3aa03896033061cc873 to your computer and use it in GitHub Desktop.
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);
}
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment