给定一个只包含'('和')'的字符串计算最长回文子串的深度即长度

虾氲叱 · 6 天前

给定一个只包含'('和')'的字符串，计算最长有效（格式正确且连续）括号子串的长度。在原问题基础上，假设字符串是分布式存储在多个节点上，每个节点存储一部分字符串，设计并实现一个分布式算法来解决该问题。请手写伪代码实现，详细描述算法思路，分析算法的时间复杂度和空间复杂度，并给出关键代码实现。

时间复杂度 O(n)
空间复杂度 O(n)

/**
   * 计算最长回文子串的深度即长度
   * @param srcStr
   * @return
   */
  public static Integer  getMaxHuiwenSubStrLen(String srcStr){
      String s = changeParenStrIntoFormatStr(srcStr);
      if (s==null){
          return null;
      }
      if (s.isEmpty()){
          return null;
      }
      if (!isHuiwenStr(s)){
          return null;
      }
      return s.length()/2;
  }

  /**
   * 把括号字符串格式化成为回文字符串
   * @param parenStr
   * @return
   */
  public static String  changeParenStrIntoFormatStr(String parenStr){
      if (parenStr==null){
          return null;
      }
      if (parenStr.isEmpty()){
          return null;
      }
      for (int i = 0; i < parenStr.length();  i++) {
          char c = parenStr.charAt(i);
          if (!(c=='(' || c== ')')){
              return null;
          }
      }
      if (!isHuiwenStr(parenStr)){
          return null;
      }
      ArrayList characters  = new ArrayList();
      for (int i = 0; i < parenStr.length();  i++) {
          char c = parenStr.charAt(i);
          if (c=='('){
              characters.add('a');
          } else if (c==')') {
              characters.add('a');
          }
      }
      StringBuilder stringBuilder = new StringBuilder();
      characters.forEach(e->{
          stringBuilder.append(e);
      });
      return stringBuilder.toString();
  }
  /**
   * 判断字符串是否是回文字符串
   * @param srcStr
   * @return
   */
  public static Boolean  isHuiwenStr(String srcStr){
      if (srcStr==null){
          return null;
      }
      if (srcStr.isEmpty()){
          return null;
      }
      if (srcStr.length()%2!=0){
          return null;
      }
      int count=0;
      for (int i = 0; i < srcStr.length()/2;  i++) {
          char c = srcStr.charAt(i);
          char c1 = srcStr.charAt(srcStr.length()  - i - 1);
          if (c==c1){
              count++;
              if (count==srcStr.length()/2){
                  break;
              }
              continue;
          }else {
              return false;
          }
      }
      return true;
  }

来源：程序园用户自行投稿发布，如果侵权，请联系站长删除
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！

账号		自动登录	找回密码
密码			立即注册

给定一个只包含'('和')'的字符串 计算最长回文子串的深度即长度

签约作者

给定一个只包含'('和')'的字符串计算最长回文子串的深度即长度