专栏首页算法修养1745. Palindrome Partitioning IV (回文树)

1745. Palindrome Partitioning IV (回文树)

题目

题意:判断一个字符串是否可以由三个回文串组成 题解:利用强大的回文树,计算出以每个字符为结尾的回文串,然后从字符串的最后一个字符开始,递归判断。

struct Tree
{
	int next[4005][30];
	int fail[4005];
	int cnt[4005];
	int num[4005];
	int len[4005];
	int s[4005];
	int p;
	int n;
	int last;

	int new_node(int x)
	{
		memset(next[p], 0, sizeof(next[p]));
		len[p] = x;
		num[p] = 0;
		cnt[p] = 0;
		
		return p++;
	}

	void init()
	{
		p = 0;
		new_node(0);
		new_node(-1);
		n = 0;
		last = 0;
		fail[0] = 1;
		s[0] = -1;
	}

	int get_fail(int x)
	{
		while (s[n - len[x] - 1] != s[n])
			x = fail[x];
		return x;
	}

	int add(int x)
	{
		x -= 'a';
		s[++n] = x;
		int cur = get_fail(last);
		if (!(last = next[cur][x]))
		{
			int now = new_node(len[cur] + 2);
			fail[now] = next[get_fail(fail[cur])][x];
			next[cur][x] = now;
			num[now] = num[fail[now]] + 1;
			cnt[now]++;
			last = now;
			return 1;
		}

		cnt[last]++;
		return 0;
	}
	void count()
	{
		for (int i = p - 1; i >= 0; i--)
		{
			cnt[fail[i]] += cnt[i];
		}
	}
};

class Solution {
public:
    vector<vector<int>> num;
bool fun(int x, int y)
{
    if(x < 0 && y < 3)
    {
        return false;
    }
	if (y == 3)
	{
		if (x == -1)
			return true;
		return false;
	}

	for (int i = 0; i < num[x].size(); i++)
	{
		if(fun(num[x][i] - 1, y + 1))
			return true;
	}
	return false;
}
    bool checkPartitioning(string s) {
        Tree tree = Tree();
	tree.init();

	for (int i = 0; i < s.length(); i++)
	{
		tree.add(s[i]);
		vector<int> m;
		int x = tree.last;
		m.push_back(i - tree.len[x] + 1);
		while (tree.fail[x] > 0)
		{
			x = tree.fail[x];
			m.push_back(i - tree.len[x] + 1);
		}

		num.push_back(m);
	}

	return fun(s.length() - 1, 0);
    }
};

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • LeetCode 1745. 回文串分割 IV(区间DP)

    给你一个字符串 s ,如果可以将它分割成三个 非空 回文子字符串,那么返回 true ,否则返回 false 。

    Michael阿明
  • palindrome - 132. Palindrome Partitioning II

    Given a string s, partition s such that every substring of the partition is a pa...

    用户5705150
  • Leetcode 132 Palindrome Partitioning II

    Given a string s, partition s such that every substring of the partition is a p...

    triplebee
  • [Leetcode][python]Palindrome Partitioning/Palindrome Partitioning II/分割回文串/分割回文串II

    将一个字符串分割成若干个子字符串,使得子字符串都是回文字符串,要求列出所有的分割方案。

    蛮三刀酱
  • Leetcode 131 Palindrome Partitioning

    Given a string s, partition s such that every substring of the partition is a p...

    triplebee
  • 常用算法整理

    王磊-AI基础
  • palindrome - 131. Palindrome Partitioning

    Given a string s, partition s such that every substring of the partition is a pa...

    用户5705150
  • ​LeetCode刷题实战132:分割回文串 II

    算法的重要性,我就不多说了吧,想去大厂,就必须要经过基础知识和业务逻辑面试+算法面试。所以,为了提高大家的算法能力,这个公众号后续每天带大家做一道算法题,题目就...

    程序IT圈
  • 回溯/贪心高频题

    "有关递归的算法,都离不开“树”的遍历这一抽象模型。只不过对于不同的算法,在前(中)后序遍历的时候,所做的事不同而已。 "

    王脸小
  • ​LeetCode刷题实战131:分割回文串

    算法的重要性,我就不多说了吧,想去大厂,就必须要经过基础知识和业务逻辑面试+算法面试。所以,为了提高大家的算法能力,题目就从LeetCode上面选 !

    程序IT圈
  • LeetCode 131 Palindrome Partitioning

    思路是,先将所有的回文子串都找出来,记录下左右端点。 然后DFS这些子串就可以了。

    ShenduCC
  • LeetCode 214. Shortest Palindrome(回文串,回文树,KMP)

    https://leetcode.com/problems/shortest-palindrome/

    ShenduCC
  • ​LeetCode刷题实战131:分割回文串

    算法的重要性,我就不多说了吧,想去大厂,就必须要经过基础知识和业务逻辑面试+算法面试。所以,为了提高大家的算法能力,这个公众号后续每天带大家做一道算法题,题目就...

    程序IT圈
  • LeetCode 132 Palindrome Partitioning II

    ShenduCC
  • 狗家算法面试高频题汇总

    Google 面试题 | Data Stream Median - Python版

    王脸小
  • [Leetcode][动态规划]相关题目汇总/分析/总结

    蛮三刀酱
  • CodeForces 17E Palisection(回文树)

    E. Palisection time limit per test 2 seconds memory limit per test 128 meg...

    ShenduCC
  • 三十分钟成为 Contributor | 提升 TiDB Parser 对 MySQL 8.0 语法的兼容性

    TiDB 的一大特性就是和 MySQL 高度兼容,目标是让用户能够无需修改代码即可从 MySQL 迁移至 TiDB。要达成这个目标,需要完成两个提升兼容性的任务...

    PingCAP
  • HDU 5157 Harry and magic string(回文树)

    Harry and magic string Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: ...

    ShenduCC

扫码关注云+社区

领取腾讯云代金券