给定一个只包含'('和')'的字符串，计算最长有效（格式精确且连续）括号子串的长度。在原问题基础上，假设字符串是分布式存储在多个节点上，每个节点存储一部分字符串，设计并实现一个分布式算法来解决该问题。请手写伪代码实现，详细形貌算法思路，分析算法的时间复杂度和空间复杂度，并给出关键代码实现。
时间复杂度 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;
}
|
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。 |
