Validate String hierarchy in Java

I have a Map, that can have keys: A, B, C, D, E, F or the subset of it

In which, A, B, C and D are a group of strings that belong to a certain hierarchy in the same order: A -> B -> C -> D

I need to check in the HashMap if the map contains a valid hierarchy. Doesn't matter in which order map stores data. I don't care about the order and I am not checking the order inside the map.

If the map contains either, it is considered a valid hierarchy:

A or
A, B or // A and B can be in any order
A, B, E or // as E is not in the group, so doesn't matter
A, B, C or // these can be in any order in map.
A, B, C, D or

If map has A, B, and D but not C, it will be considered invalid.

I can add multiple if else check, but this will make code messy. Is there any elegant way of doing this check?

Edit: I have implemented below logic:


// order contains strings in order: { A, B, C, D}
private boolean isHierarchyComplete(Map<String, Object> map, String[] order) {

    // lastIndexFound, this will give the last index of string found in hierarchy that is continous and breaks out once the path is broken
    int lastIndexFound = -1;
    for (String str : order) {
      if (map.containsKey(str)) {
        lastIndexFound++;
      } else {
        break;
      }
    }

    // if nothing found from path
    if (lastIndexFound == -1) {
      return false;
    }
    
    // if all found from path
    if (lastIndexFound == order.length - 1) {
      return true;
    }
    // now check after lastIndexFound if there are any values from hierarchy,
    // if present return false
    for (int index = lastIndexFound + 1; index < order.length; index++) {
      if (map.containsKey(order[index])) {
        return false;
      }
    }

    return true;
  }

Solution

I think the problem can be solved in the following way (a working demonstration),

import java.util.HashMap;

public class MyClass {
    public static void main(String args[]) {
        String[] hierarchy = {"A","B","C","D"};
        
        //Test case 1: false
        HashMap<String,String> map = new HashMap<String,String>();
        map.put("A","#");
        map.put("D","#");
        isValidMap(map,hierarchy);
        map = new HashMap<String,String>();
        
        //Test case 2: true
        map = new HashMap<String,String>();
        map.put("A","#");
        map.put("B","#");
        isValidMap(map,hierarchy);
        map = new HashMap<String,String>();
        
        //Test case 3: true
        map = new HashMap<String,String>();
        map.put("E","#");
        map.put("F","#");
        isValidMap(map,hierarchy);
        map = new HashMap<String,String>();
        
        //Test case 4: true
        map = new HashMap<String,String>();
        map.put("A","#");
        map.put("E","#");
        isValidMap(map,hierarchy);
        map = new HashMap<String,String>();
        
        //Test case 5: true
        map = new HashMap<String,String>();
        map.put("A","#");
        map.put("B","#");
        map.put("C","#");
        isValidMap(map,hierarchy);
        map = new HashMap<String,String>();
        
        //Test case 6: true
        map = new HashMap<String,String>();
        map.put("A","#");
        map.put("B","#");
        map.put("E","#");
        isValidMap(map,hierarchy);
        map = new HashMap<String,String>();
        
        //Test case 7: false
        map = new HashMap<String,String>();
        map.put("A","#");
        map.put("D","#");
        map.put("E","#");
        isValidMap(map,hierarchy);
        map = new HashMap<String,String>();
        
    }
    
    public static void isValidMap(HashMap<String,String> map, String[] hierarchy){
        boolean checkShouldBePresent = true;
        boolean finalAns = true;
        boolean changed = false;
        boolean checked = false;
        for(int i=0;i<hierarchy.length;i++){
            String s = hierarchy[i];
            
            boolean finalAnsPrev = finalAns;
            finalAns = finalAns && !changed?map.keySet().contains(s):!map.keySet().contains(s);
            
            
            if(finalAnsPrev!=finalAns && !checked){
                changed = true;
                finalAns = true;
                checked = true;
            }
        }
        
        System.out.println(finalAns);
    }
}

the main logic above is in the isValidMap method.

Explanation:

The logic for solving the problem is as follows,

We should traverse the hierarchy elements one by one starting from the top and check if it is present in the given map keyset. The moment when we find one of the elements in the hierarchy is missing in the map, all the following elements should not be present as well.

For example,

String[] hierarchy = {"A","B","C","D"};

//keyset = set of {"A", "B", "E"}. The truth list of the hierarchy elements pertaining to whether they are present in the keyset or not is,
[A:TRUE,B:TRUE,C:FALSE,D:FALSE]     ... (1)

//keyset = set of {"G", "F", "E"}. The truth list of the hierarchy elements pertaining to whether they are present in the keyset or not is,
[A:FALSE,B:FALSE,C:FALSE,D:FALSE].  ... (2)

//keyset = set of {"A", "B", "D"}. The truth list of the hierarchy elements pertaining to whether they are present in the keyset or not is,
[A:TRUE,B:TRUE,C:FALSE,D:TRUE].  ... (3)

In example (3) above, notice how there is a change in truth values from TRUE to FALSE and then again to TRUE. In all such cases, we would say that the map keyset does not obey our hierarchy.

The time complexity should also be O(n) where n is the length of the hierarchy array.