给定一个字符串 str,设计一个算法采用顺序栈判断 str 是否为形如“序列 1@序列 2”的合法字符 串,其中序列 2 是序列 1 的逆序,str 中恰好只有一个@字符。 java
时间: 2024-10-19 18:14:05 浏览: 33
JS使用栈判断给定字符串是否是回文算法示例
5星 · 资源好评率100%
要判断给定字符串 `str` 是否满足“序列 1@序列 2”且序列 2 是序列 1 的逆序这一条件,你可以按照以下步骤使用 Java 实现:
1. 定义两个指针,`start` 和 `end` 分别指向字符串开始和`str.indexOf('@') + 1`的位置(跳过 '@' 符号)。这两个指针用于遍历序列 1 和序列 2。
2. 使用一个顺序栈 `stack` 存储序列 1 的字符。从 `start` 开始,依次将字符入栈,直到遇到 `end`。
3. 当遍历到 `end` 位置后,如果栈为空,则说明 `str` 不合法,因为序列 1 应该包含至少一个字符。此时返回 false。
4. 然后,清空栈并更新 `start = end + 1`,`end = str.length()`。接下来,检查从 `start` 到 `end` 的字符是否是序列 1 的逆序。如果发现任何一个字符与栈顶元素不符,或者栈为空而当前字符不是 ' '(空格),则 `str` 不合法,返回 false。
5. 如果最终能够遍历完整个字符串且栈始终只包含一个字符,那么 `str` 就是合法的,返回 true。
以下是对应的 Java 代码示例:
```java
import java.util.Stack;
public class Main {
public static boolean isValid(String str) {
if (str == null || str.isEmpty() || str.contains("@") != 1) {
return false;
}
int start = 0, end = str.indexOf('@');
Stack<Character> stack = new Stack<>();
for (int i = start; i < end; i++) {
stack.push(str.charAt(i));
}
start = end + 1;
end = str.length();
while (start < end) {
char top = stack.empty() ? ' ' : stack.pop();
if (top != ' ' && top != str.charAt(start)) {
return false;
}
start++;
}
// 栈里仅剩一个字符,即序列1的最后一个字符
return stack.size() == 1;
}
public static void main(String[] args) {
System.out.println(isValid("ab@ba")); // true
System.out.println(isValid("ab@b")); // false
System.out.println(isValid("a@b")); // false
}
}
```
阅读全文