时间戳

首页 > 解决方案 > 在 Java 中验证字符串层次结构

java - 在 Java 中验证字符串层次结构

问题描述

我有一个地图，它可以有键：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

如果maphasA, B, and D但 not 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;
  }

标签： javapredicate

解决方案

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

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 是层次结构数组的长度。

推荐阅读