Longest Uncommon Subsequence

发表于 | 分类于

Longest Uncommon Subsequence(最长非公共子序列)

题目描述：

给定两个字符串，找到两个字符串的最长非公共子序列。其中子序列的定义为：原序列中删除部分字符所得到，即原始序列中的字符顺序不改变。即假设字符串str1和str2。找到str1中的最长子序列，且该序列无法由str2得到。另外我们设定str1和””都是str1的子序列。如果”aa”和”aa”的话，不存在非公共子序列，返回-1.

例子：

“abc”和”cdc”的最长子序列是”abc”(“cdc”)。所以最长的非公共子序列长度为3.见LeetCode521

解题思路：

初看题目会陷入困局；想要找到”abc”中的所有子序列然后和”cdc”一一验证。但是其实我们从另外一个角度看，我们可以先将两个字符串相同的情况排除后;在两个字符串不同长度的情况下，肯定是较长的字符串的本身是我们需要的结果。因为较长的字符串肯定无法通过另外一个串得到，所以较长的串就是我们所求的。

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
class Solution {
public:
    int findLUSlength(string a, string b) {
        if(a == b) return - 1;
        int res = a.size();
        for (int i = 0; i < a.size(); i++){
            for (int j = i; j < a.size(); j++){
                if (sub(a.substr(i, j - i + 1), b)){
                    res = max(res, j - i + 1);
                }
            }
        }//判断str1的子序列是不是str2的子序列
        for (int i = 0; i < b.size(); i++){
            for (int j = i; j < b.size(); j++){
                if (sub(b.substr(i, j - i + 1), a)){
                    res = max(res, j - i + 1);
                }
            }
        }//判断str2的子序列是不是str1的子序列
        return res;
        
    }
    bool sub(string source, string target){
        for (int i = 0; i < source.size(); i++){
            int j = 0;
            while(j < target.size() && target[j] != source[i]){
                j++;
            }
            if (j >= target.size()) return false;
            else{
                j++;
            }
        }
        return true;
        //判断两个串的互为子序列关系
    }
};
class Solution {
public:
    int findLUSlength(string a, string b) {
        return (a == b) ? -1: max(a.size(), b.size());
        //直接返回较长的串的长度即可。
    }
};

Longest Uncommon Subsequence II(最长非公共子序列)

题目描述：

给定一个字符串数组，找到字符串数组中的最长非公共子序列。

例子：

“abc”, “cde”, “fgh”的最长公共子序列的长度是3，任意的一个字符串都是最长非公共子序列。

解题思路：

与上一题类似，我们想直接利用最长的那个字符来作为结果返回；但是”aaa”,”aaa”,”bb”这样的情况导致结果不符合题意；所以需要利用哈希表来过滤掉超过两次的字符串；但是仅仅这样还是不够；因为如果输入是”aaa”,”aaa”,”aa”这样的情况下是不存在所谓的非公共子序列。所以思路是我们找到一个字符串，判断它是否是最长公共子序列的方法是与比它长的字符串比较，只有它不是所有比它长的字符串的子序列才可以成为最长子序列。

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
bool cmp(pair<string, int> &a, pair<string, int>&b){
    return a.first.size() > b.first.size();
}
//作为sort函数的比较；按照字符串的长度排序，由高到低。
bool s1SubOfs2(string s1, string s2){
    int i = 0;
    int j = 0;
    for (;i < s1.size(); i++){
        while(j < s2.size() && s2[j] != s1[i]) j++;
        if (j == s2.size()) return false;
        j++;
    }
    return true;
}
// 判断s1是不是s2的子序列函数
class Solution {
public:
    int findLUSlength(vector<string>& strs) {
        unordered_map<string, int> hash;
        vector<pair<string, int>> vec;
        for (auto str : strs) hash[str]++;
        //用哈希表将字符串保存，value是字符串出现的次数
        
        for (auto it = hash.begin(); it != hash.end(); it++){
            vec.push_back(*it);
        }
        //用vector保存string和次数，便于利用cmp函数的排序
        sort(vec.begin(), vec.end(), cmp);
        //利用cmp函数排序
        for (int i = 0; i < vec.size(); i++){
            if (vec[i].second == 1){
            //过滤掉超过两次的字符串
                int j = 0;
                for (; j < i; j++){
                    if (s1SubOfs2(vec[i].first, vec[j].first)) break;
                    //将当前字符串和比它长的串一一比较；
                }
                if (j == i) return vec[i].first.size();
                //当它与比它长的字符串都不是子序列关系后返回
            }
        }
        return -1;
        //如果不存在返回-1.
        
    }
};