521. Longest Uncommon Subsequence I

左手的ㄟ右手 2022-06-02 00:29 112阅读 0赞

[原题链接][Link 1]

## 1 蛮力破解（Time Limit Exceeded） ##

暴力破解方式将会生成所有的 2n个子序列。并且将他们的复现次数也一同存储到hashmap中。最长的子序列的复现次数一定为1，如果没有找到复现次数为1的序列，则返回-1

ublic class Solution {
        public int findLUSlength(String a, String b) {
            HashMap < String, Integer > map = new HashMap < > ();
            for (String s: new String[] {a, b}) {
                for (int i = 0; i < (1 << s.length()); i++) {
                    String t = "";
                    for (int j = 0; j < s.length(); j++) {
                        if (((i >> j) & 1) != 0)
                            t += s.charAt(j);
                    }
                    if (map.containsKey(t))
                        map.put(t, map.get(t) + 1);
                    else
                        map.put(t, 1);
                }
            }
            int res = -1;
            for (String s: map.keySet()) {
                if (map.get(s) == 1)
                    res = Math.max(res, s.length());
            }
            return res;
        }
    }

**代码位运算解释**

> 假设给定一个字符串”abc”  
> 这个字符串给以让i 从0迭代到 2^3-1 =1<<3 -1 = 7 个  
> i subsequence  
> 000 “”  
> 001 “a”  
> 010 “b”  
> 011 “ab”  
> 100 “c”  
> 101 “ac”  
> 110 “bc”  
> 111 “abc”  
> **if (((i >> j) & 1) != 0)** 这个条件用于检查第j位是否为1。

## 2 建议解法（AC） ##

对输入进行一个简易的分析。  
假定输入的两个string分别为a和b

*  a = b。如果两个序列完全相等，则返回-1
 *  如果两个序列的长度相等 length(a) = length(b)，但是两个序列的内容不等，即 a ！= b。那么返回的值则为 length(a) 或者 length(b)
 *  如果a, b的序列长度不等，则更长的序列就是我们需要的最长的，且只出现一次的序列，为此返回值为max(length(a),length(b)).

public class Solution {
        public int findLUSlength(String a, String b) {
            if (a.equals(b))
                return -1;
            return Math.max(a.length(), b.length());
        }
    }

[Link 1]: https://leetcode.com/problems/longest-uncommon-subsequence-i/description/