516. 最长回文子序列

布满荆棘的人生 2023-10-04 09:35 8阅读 0赞

给定一个字符串 `s` ，找到其中最长的回文子序列，并返回该序列的长度。可以假设 `s` 的最大长度为 `1000` 。

**示例 1:**  
输入:

"bbbab"

输出:

一个可能的最长回文子序列为 "bbbb"。

**示例 2:**  
输入:

"cbbd"

输出:

一个可能的最长回文子序列为 "bb"。

**提示：**

*  `1 <= s.length <= 1000`
 *  `s` 只包含小写英文字母

package Solution516;
    
    import java.math.BigInteger;
    
    class Solution2 {
    	public int longestPalindromeSubseq(String s) {
    		int max = 0;
    		int n = s.length();
    		/* Number of subsequences is (2**n -1) */
    		int opsize = (int) Math.pow(2, n);
    
    		/* Run from counter 000..1 to 111..1 */
    		for (int counter = 1; counter < opsize; counter++) {
    			String temp = "";
    			for (int j = 0; j < n; j++) {
    				/*
    				 * Check if jth bit in the counter is set If set then print jth element from
    				 * arr[]
    				 */
    
    				if (BigInteger.valueOf(counter).testBit(j)) {
    
    					temp = temp + s.charAt(j);
    				}
    			}
    			// System.out.println(temp);
    			if (isPalindrome(temp)) {
    				if (temp.length() > max) {
    					max = temp.length();
    				}
    
    			}
    
    		}
    		return max;
    
    	}
    
    	public boolean isPalindrome(String s) {
    		int mid = s.length() / 2;
    		int index = 0;
    		while (index < mid) {
    			char i = s.charAt(index);
    			char j = s.charAt(s.length() - 1 - index);
    			if (i == j) {
    				index++;
    			} else {
    				return false;
    			}
    		}
    		return true;
    	}
    
    	public static void main(String[] args) {
    
    		Solution2 sol = new Solution2();
    
    		String s = "bbbab";
    
    		System.out.println(sol.longestPalindromeSubseq(s));
    	}
    
    }

上面代码超时

package Solution516;
    
    import java.math.BigInteger;
    import java.util.Arrays;
    
    class Solution {
    	public int longestPalindromeSubseq(String s) {
    		int n = s.length();
    		/* Number of subsequences is (2**n -1) */
    		int opsize = (int) Math.pow(2, n);
    		int[] arr = new int[opsize];
    		/* Run from counter 000..1 to 111..1 */
    		for (int counter = 1; counter < opsize; counter++) {
    			arr[counter] = counter;
    		}
    		Arrays.sort(arr);
    		String istr = "";
    		int icount = 0;
    		int[] index = new int[arr.length];
    		int maxcount = 0;
    		for (int i = 0; i < arr.length; i++) {
    			icount = 0;
    			istr = Integer.toBinaryString(arr[i]);
    			for (int k = 0; k < istr.length(); k++) {
    				if (istr.charAt(k) == '1') {
    					icount++;
    				}
    			}
    			if (icount > maxcount) {
    				maxcount = icount;
    			}
    			index[i] = icount;
    		}
    		for (int i = maxcount; i > 0; i--) {
    			for (int k = 0; k < arr.length; k++) {
    				if (index[k] == i) {
    					String temp = "";
    					for (int j = 0; j < n; j++) {
    						/*
    						 * Check if jth bit in the counter is set If set then print jth element from
    						 * arr[]
    						 */
    						if (BigInteger.valueOf(arr[k]).testBit(j)) {
    							temp = temp + s.charAt(j);
    						}
    					}
    					if (isPalindrome(temp)) {
    						return i;
    					}
    				}
    			}
    		}
    		return 0;
    	}
    
    	public boolean isPalindrome(String s) {
    		int mid = s.length() / 2;
    		int index = 0;
    		while (index < mid) {
    			char i = s.charAt(index);
    			char j = s.charAt(s.length() - 1 - index);
    			if (i == j) {
    				index++;
    			} else {
    				return false;
    			}
    		}
    		return true;
    	}
    
    	public static void main(String[] args) {
    
    		Solution sol = new Solution();
    
    		String s = "bbbab";
    
    		System.out.println(sol.longestPalindromeSubseq(s));
    	}
    
    }

上面代码超出内存