[LintCode] Longest Repeating Subsequence

Karuru 发布于2019-08-15 13:37 / 1209人阅读

摘要：用二维数组进行动态规划，作为第位和的位已有的重复子序列长度最大值计数器。

Problem

Given a string, find length of the longest repeating subsequence such that the two subsequence don’t have same string character at same position, i.e., any ith character in the two subsequences shouldn’t have the same index in the original string.

Example

str = abc, return 0, There is no repeating subsequence

str = aab, return 1, The two subsequence are a(first) and a(second).
Note that b cannot be considered as part of subsequence as it would be at same index in both.

str = aabb, return 2

Solution

用二维数组进行动态规划，作为第i位和的j位已有的重复子序列长度最大值计数器。

public class Solution {
    /*
     * @param str: a string
     * @return: the length of the longest repeating subsequence
     */
    public int longestRepeatingSubsequence(String str) {
        int n = str.length();
        int[][] dp = new int[n+1][n+1];
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                if (i != j && str.charAt(i-1) == str.charAt(j-1)) {
                    dp[i][j] = dp[i-1][j-1] + 1;
                } else {
                    dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]);
                }
            }
        }
        return dp[n][n];
    }
}

idc机房托管私有云 Repeating Subsequence Longest LintCode

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/68210.html

[LintCode] Longest Increasing Subsequence

Problem Given a sequence of integers, find the longest increasing subsequence (LIS). You code should return the length of the LIS. Clarification Whats the definition of longest increasing subsequence?...

Flands 2019-08-14 14:22 评论0 收藏0
[LintCode] Longest Substring Without Repeating Cha

摘要：哈希表法双指针法只有当也就是时上面的循环才会结束，，跳过这个之前的重复字符再将置为 Problem Given a string, find the length of the longest substring without repeating characters. Example For example, the longest substring without repeat...

Scliang 2019-08-14 15:19 评论0 收藏0
[Lintcode] Longest Increasing Subsequence 最长上升序列

摘要：样例给出，这个是，返回给出，这个是，返回挑战要求时间复杂度为或者说明最长上升子序列的定义最长上升子序列问题是在一个无序的给定序列中找到一个尽可能长的由低到高排列的子序列，这种子序列不一定是连续的或者唯一的。 Longest Increasing Subsequence 本文最新版本位于 https://yanjia.me/zh/2018/11/... 给定一个整数序列，找到最长上升子序...

hlcc 2019-08-14 12:41 评论0 收藏0
[LintCode] Longest Increasing Continuous Subseque

摘要：最长连续递增递减子序列，设置正向计数器，后一位增加则计数器加，否则置。反向计数器亦然。每一次比较后将较大值存入。 Problem 最长连续递增／递减子序列 Give an integer array，find the longest increasing continuous subsequence in this array.An increasing continuous subs...

wwq0327 2019-08-14 15:11 评论0 收藏0
[Leetcode]Longest Substring Without Repeating Char

摘要：解题思路本题借助实现。如果字符未出现过，则字符，如果字符出现过，则维护上次出现的遍历的起始点。注意点每次都要更新字符的位置最后返回时，一定要考虑到从到字符串末尾都没有遇到重复字符的情况，所欲需要比较下和的大小。 Longest Substring Without Repeating CharactersGiven a string, find the length of the lon...

awesome23 2019-08-16 10:26 评论0 收藏0