给定一个只包含'('和')'的字符串,计算最长有效(格式正确且连续)括号子串的长度。在原问题基础上,假设字符串是分布式存储在多个节点上,每个节点存储一部分字符串,设计并实现一个分布式算法来解决该问题。请手写伪代码实现,详细描述算法思路,分析算法的时间复杂度和空间复杂度,并给出关键代码实现。
时间复杂度 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<Character> 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; } |
---|
原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。
如有侵权,请联系 cloudcommunity@tencent.com 删除。
原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。
如有侵权,请联系 cloudcommunity@tencent.com 删除。