首页 > 小红书9.12 笔试第二题
头像
首夏犹清和
编辑于 2020-09-12 12:24
+ 关注

小红书9.12 笔试第二题

给定一个非空字符串s,切割成若干个首尾相同的非空子串,求最少字串数量。

样例:
abaccd
输出:
3

100%AC答案:
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		String s = in.nextLine();
                //构建dp数组,dp[i]代表的是前i个字符所能切成的最少字串数量
                //比如: dp[4]代表的就是前4个字符,也就是dp[0]-dp[3]所切割的最少字串数量
		int[] dp = new int[s.length()+1];
		char[] chr = s.toCharArray();
                //前i个字符能切的最大子串数量
                //比如前3个字符最多能切三次
		for (int i = 0; i <= s.length(); ++i) {
			dp[i] = i;
		}
		dp[0] = 0;
                //遍历字符数组
		for (int i = 1;i<=s.length();i++){
                        //从后向前找,找到与当前s[i]相同的字符
			for (int j = s.length(); j >= i; --j) {
                                //如果找到相同字符,进行状态转移
				if (chr[i-1] == chr[j-1]) {
					dp[j] = Math.min(dp[j],dp[i-1] + 1);
				}
			}
		}
		System.out.println(dp[s.length()]);
	}
}        


全部评论

(1) 回帖
加载中...
话题 回帖

推荐话题

相关热帖

近期热帖

历年真题 真题热练榜 24小时
技术(软件)/信息技术类
查看全部

近期精华帖

热门推荐