验证 Java 中的字符串层次结构

Question

我有一个地图，它可以有键：A, B, C, D, E, F或其子集

其中，A, B, C and D是一组属于某一层级且顺序相同的字符串：A -> B -> C -> D

我需要检查 HashMap 地图是否包含有效的层次结构。地图存储数据的顺序无关紧要。我不关心顺序，也不检查地图内的顺序。

如果地图包含其中任何一个，则它被认为是有效的层次结构：

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

如果map有A, B, and D但没有C，则视为无效

我可以添加多个if else检查，但这会使代码变得混乱。有什么优雅的方法可以做这个检查吗？

编辑：我已经实现了以下逻辑：


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

Answer 1

所以基本上你有一些不能出现的键，除非它们的“父”键也在那里：

String[] keyHierarchy = "A B C D".split(" ");

并且您正在实施类似于

的内容

boolean hasValidKeysAsPerHierarchy(Set<String> keySet, ArrayList<String> hierarchy) { ... }

请注意，您可以使用 m.keySet() 从 Map<String, Anything> m 中获取一组密钥；您还可以通过以下方式将 String[] a 转换为 List<String> l Arrays.asList(a)

这可以通过首先找到键集中的最后一个层级键，然后检查是否存在所有其他层级更小的键来实现。

boolean hasValidKeysAsPerHierarchy(Set<String> keySet, List<String> hierarchy) {
    int lastHKPos = -1;
    for (String k : keySet) {
        lastHKPos= Math.max(hierarchy.indexOf(k), lastHKPos);
    }
    // now, we need to find all hierarchy-keys from 0 to lastHKPos, exclusive
    for (int i=0; i<lastHKPos; i++) {
        String hKey = hierarchy.get(i);
        if ( ! keySet.contains(hKey)) return false; // missing hierarchy-key!
    }
    return true; // no missing hierarchy-keys
}

如果层次结构（我们称之为 h）非常大，您可以通过构建辅助 O(n * h) 到 O(n * log(h)) 来加速第一个 for 循环 Map<String,Integer> 将层次结构键映射到它们在层次结构中的位置。

Answer 2

我认为可以通过以下方式解决问题（工作演示），

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

上面的主要逻辑在isValidMap方法中。

解释：

解题逻辑如下，

我们应该从顶部开始逐个遍历层次结构元素，并检查它是否存在于给定的 map 键集中。当我们发现层次结构中的一个元素在地图中丢失时，以下所有元素也不应该存在。

例如，

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)

在上面的示例 (3) 中，请注意真值如何从 TRUE 变为 FALSE，然后再次变为 TRUE。在所有这些情况下，我们会说映射键集不服从我们的层次结构。

时间复杂度也应该是O(n)，其中n是层级数组的长度。

验证 Java 中的字符串层次结构

Validate String hierarchy in Java

java

predicate