Real-time Example

String Loop

Input: String[] = {"NAME1", "NAME2, … "NAME n"}

Output: boolean if it's possible to arrange names into a loop

Solution:

1. n levels, each level decides a specific position that was sit by two people

2. each level has at most n possible branches

TC: n = # of names O(n! *name.length)

SC: O(n)

public class Solution {
   public boolean isLoop(String[] input) {
       if (input == null) {
           return false;
       }
       return dfs(input, 1);
   }

   private boolean dfs(String[] input, int index) {
       //base case
       if (index == input.length) {
           return canSit(input[index - 1], input[0]);
       }

       for (int i = index; i < input.length; i++) {
           if (canSit(input[index - 1], input[i])) {
               swap(input, index, i);
               if (dfs(input, index + 1)) {
                   return true;
               }
               swap(input, index, i);
           }
       }
       return false;
   }

   private boolean canSit(String a, String b) {
       return Objects.equals(a.charAt(a.length() - 1), b.charAt(0));
   }

   private void swap(String[] input, int left, int right) {
       String tmp = input[left];
       input[left] = input[right];
       input[right] = tmp;
   }


   public static void main(String[] args) {
       String[] names = {"ALICE", "CHARLES", "ERIC", "SOPHIA"};
       Solution res = new Solution();
       System.out.println(res.isLoop(names));
   }
}