难度中等

给你一个字符串 s ，请你判断它是否有效。

字符串 s 有效需要满足：假设开始有一个空字符串 t = "" ，你可以执行 任意次 下述操作将 t 转换为 s ：

将字符串 "abc" 插入到 t 中的任意位置。形式上， t 变为 tleft + "abc" + tright ，其中 t == tleft + tright 。注意， tleft 和 tright 可能为空。

如果字符串 s 有效，则返回 true ；否则，返回 false 。

示例 1：

输入：s = "aabcbc"

输出：true

解释：

"" -> "abc" -> "aabcbc"

因此，"aabcbc" 有效。

示例 2：

输入：s = "abcabcababcc"

输出：true

解释：

"" -> "abc" -> "abcabc" -> "abcabcabc" -> "abcabcababcc"

因此，"abcabcababcc" 有效。

示例 3：

输入：s = "abccba"

输出：false

解释：执行操作无法得到 "abccba" 。

提示：

# 栈

	class Solution {
	public boolean isValid(String s) {
	// 栈
	Deque<Character> stack = new LinkedList<>();
	int n = s.length();
	for (int i = 0; i < n; i++) {
	char cur = s.charAt(i);
	if (cur != 'c') {
	stack.offerFirst(cur);
	continue;
	}
	// 遇到 c 必须弹 2 个，a b
	int cnt = 0;
	while (!stack.isEmpty() && stack.peekFirst() == cur - 1) {
	cur = stack.pollFirst();
	cnt++;
	}
	if (cnt != 2) {
	return false;
	}
	}
	return stack.isEmpty();
	}
	}

# 数组模拟栈

遇到 a：入栈

遇到 b：若栈顶为空或者栈顶不为 a，false

遇到 c：若栈顶为空或者栈顶不为 b，false

	class Solution {
	public boolean isValid(String s) {
	// 栈
	int n = s.length();
	char[] st = new char[n];
	int len = 0;
	for (int i = 0; i < n; i++) {
	char cur = s.charAt(i);
	//a：入栈
	//b：若栈顶为空或者栈顶不为 a，false
	// a 出栈，b 入栈
	//c：若栈顶为空或者栈顶不为 b，false
	if (cur > 'a') {
	if (len == 0 \|\| st[len - 1] != cur - 1) {
	return false;
	}
	len--;
	}
	if (cur < 'c') {
	st[len++] = cur;
	}
	}
	return len == 0;
	}
	}

遇到 a 就添加 "abc"

例如："aabcbc"

	class Solution {
	public boolean isValid(String s) {
	MyLinkedList list = new MyLinkedList();
	/// 遇到一个 a 就添加
	int n = s.length();
	Node cur = null;
	Node prev = null;
	for (int i = 0; i < n; i++) {
	if (s.charAt(i) == 'a') {
	// 当前节点
	cur = list.add(prev, 'a');
	Node b = list.add(cur, 'b');
	list.add(b, 'c');
	}
	if (cur == null \|\| s.charAt(i) != cur.v) {
	return false;
	}
	prev = cur;
	cur = cur.next;
	}
	if (cur != null) {
	return false;
	}
	return true;
	}
	}
	class MyLinkedList {
	Node head;
	Node tail;
	int len;
	public MyLinkedList() {
	head = new Node(-1);
	tail = head;
	}
	public Node addTail(int v) {
	Node newNode = new Node(v);
	tail.next = newNode;
	tail = newNode;
	len++;
	return newNode;
	}
	public Node add(Node node, int v) {
	if (node == null) {
	return addTail(v);
	}
	Node newNode = new Node(v);
	newNode.next = node.next;
	node.next = newNode;
	len++;
	return newNode;
	}
	}

	class Node {
	int v;
	Node next;
	public Node(int v) {
	this.v = v;
	}
	public Node(int v, Node next) {
	this.v = v;
	this.next = next;
	}
	}