CodingGame - SomeonesActingSus.md

Someone's Acting 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

Solution.java

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);
            }
        }
    }
}