leetCode 字符串相关问题

125. 验证回文串

/*
* 给定一个字符串，验证它是否是回文串，只考虑字母和数字字符，可以忽略字母的大小写。
* 输入: "A man, a plan, a canal: Panama"
输出: true
回文串：正读和反读都是一样的字符串。
* */

 public boolean isPalindrome2(String s){

//		对初始字符串进行预处理

		 s=s.toLowerCase();

		 int low=0;

		 int high=s.length()-1;

		 while(low<high){

			 if(!Character.isLetterOrDigit(s.charAt(low))) low++;

			 else if(!Character.isLetterOrDigit(s.charAt(high))) high--;

			 else if(s.charAt(low)!=s.charAt(high)) return false;

			 else{

				 low++;

				 high--;

			 }

		 }

		 return true;

	 }

28. 实现strStr()

实现 strStr() 函数。

给定一个 haystack 字符串和一个 needle 字符串，在 haystack 字符串中找出 needle 字符串出现的第一个位置 (从0开始)。如果不存在，则返回 -1。

暴力求解方法：

public int strStr(String haystack, String needle) {

//		暴力解法

        if(needle.isEmpty()) return -1;

        final int N=haystack.length()-needle.length()+1;

        for(int i=0;i<N;i++){

        	int j=i;

        	int k=0;

        	while(j<haystack.length() && k<needle.length() && haystack.charAt(j)==needle.charAt(k)){

        		k++;

        		j++;

        	}

        	if(k==needle.length()){

        		return i;

        	}

        }

        return -1;

    }

67. 二进制求和

/*
* 给定两个二进制字符串，返回他们的和（用二进制表示）。

输入为非空字符串且只包含数字 1 和 0。
* */

 public String addBinary(String a, String b) {

        StringBuilder result=new StringBuilder();

		int i=a.length()-1;

		int j=b.length()-1;

		int carry=0;

		while(i>=0 || j>=0 || carry>0){

			int valueA=i<0 ? 0: a.charAt(i--)-'0';

			int valueB=j<0 ? 0: b.charAt(j--)-'0';

			int sum=valueA+valueB+carry;

			result.insert(0, Character.forDigit(sum%2, 10));

			carry=sum/2;

		}

		return result.toString();

    }

5. 最长回文子串

给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。

策略：

A:暴力求解：时间复杂度是o(n*2)

B:记忆化搜索：复杂度 O(n^2) 。设 f[i][j] 表示[i,j]之间的最长回文子串，递推方程如下：

f[i][j] = if (i == j) S[i]
if (S[i] == S[j] && f[i+1][j-1] == S[i+1][j-1]) S[i][j]
else max(f[i+1][j-1], f[i][j-1], f[i+1][j])

C:动态规划算法：

设状态为 f(i,j) ，表示区间[i,j]是否为回文串，则状态转移方程为

	/*

	 * 动态规划问题经常用于求解最优子结构以及重叠子问题，以前我们经常将重叠子问题

	 * 使用递归进行实现，但是有问题的是，会进行大量重复的计算，而动态规划就是将之前的结果保存下来，避免了不必要的

	 * 重复操作，提升了效率。

	 *

	 * 实现原理：

	 * 借助一个二维布尔数组

	 * 每个dp[i][j]表示一个方格，每个方格中的T与F分别表示当前子串是否是

	 * 回文字符串。

	 * 再进行转换的时候，表达式即是str[i]==str[j] && dp[i+1][j-1]

	 * */

	public String longestPalindrome3(String s){

		int len=s.length();

		int maxlen=0;

		String res=null;

		boolean [][] dp=new boolean[len][len];

		for(int i=len-1;i>=0;i--){

			for(int j=i;j<len;j++){

				dp[i][j]=s.charAt(i)==s.charAt(j)  && (j-i<3 || dp[i+1][j-1]);

				if(dp[i][j] && (res==null || j-i+1>maxlen)){

					res=s.substring(i,j+1);

					maxlen=res.length();

				}

			}

		}

		return res;

	}

巴特西

leetCode 字符串相关问题

125. 验证回文串

28. 实现strStr()

67. 二进制求和

5. 最长回文子串

最新文章

热门文章