算法精选题总结之字符串类
2019-02-03 本文已影响60人
码上就说
1.字符串旋转
2.字符串包含
3.字符串的全排列
4.字符串转换成整数
5.回文判断
6.最长回文子串
1.字符串旋转
给定一个字符串，要求将字符串前面的若干个字符移到字符串的尾部，例如，将字符串"abcdef"的前3个字符'a' 'b' 'c'移到字符串的尾部，那么原字符串将变成"defabc"，请写一个函数实现此功能。
首先将字符串 abcdef 分为两部分， abc 与 def，分别对abc逆序和def逆序，得到的结果如下：cbafed，然后对整个字符串逆序，得到的结果如下：defabc，源码如下：
//Author:jeffmony@163.com
public class StringTest {
public static void main(String[] args) {
Solution instance = new Solution();
String string = "abcdefg";
char[] src = string.toCharArray();
instance.leftRotateString(src, src.length, 3);
for(int i=0;i<src.length;i++) {
System.out.print(src[i]);
}
System.out.println();
}
}
class Solution {
public void ReverseString(char[] src, int from, int to) {
while(from < to) {
char temp = src[from];
src[from] = src[to];
src[to] = temp;
from++;
to--;
}
}
public void leftRotateString(char[] src, int n, int m) {
m %= n;
ReverseString(src, 0, m-1);
ReverseString(src, m , n-1);
ReverseString(src, 0, n-1);
}
}
2.字符串包含
给定一个长字符串a和一字符串b，请问，如何快速地判断出短字符串b中的所有字符串是否都在长字符串a中？
例如，a字符串是"ABCD"，b字符串是"BAD"，答案是true，因为字符串b中的所有字母都在字符串a中。
解法一：素数相乘
总共26个英文字母，我们可以用前26个素数表示这26个英文字母，因为素数是乘法中一种非常重要的概念。
如果判断b字符串是否是a字符串的子集，只需要判断a字符串代表的素数的乘积是否能整除b字符串代表的素数乘积。
//Author:jeffmony@163.com
public class StringTest {
public static void main(String[] args) {
Solution instance = new Solution();
String A = "ABCDEFG";
char[] a = A.toCharArray();
String B = "FFV";
char[] b = B.toCharArray();
boolean result = instance.StringContains(a,b);
System.out.println("result = " + result);
}
}
class Solution {
public static final int[] p= new int[]{2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101};
public boolean StringContains(char[] a, char[] b) {
int f = 1;
for (int i=0;i<a.length;i++) {
int x = p[a[i]-'A'];
if (f%x!=0){
f *=x;
}
}
for (int i=0;i<b.length;i++) {
int x = p[b[i]-'A'];
if (f%x!=0) {
return false;
}
}
return true;
}
}
这种做法也是有问题的，因为乘法毕竟是比较耗时的操作，而且很多的素数相乘会导致溢出。
解法二：位运算
26个英文字母，可以看成26个位，如果当前字符存在，则在相应的位置1，a字符串生成一个hash位，然后使用这个hash位于b字符串对应的位相与，可以判断得到结果。
//Author:jeffmony@163.com
public class StringTest {
public static void main(String[] args) {
Solution instance = new Solution();
String A = "ABCDEFG";
char[] a = A.toCharArray();
String B = "FFB";
char[] b = B.toCharArray();
boolean result = instance.StringContains(a,b);
System.out.println("result = " + result);
}
}
class Solution {
public boolean StringContains(char[] a, char[] b) {
int hash = 0;
for(int i=0;i<a.length;i++) {
hash |= (1<<(a[i]-'A'));
}
for(int i=0;i<b.length;i++) {
if((hash&(1<<(b[i]-'A')))==0){
return false;
}
}
return true;
}
}
3.字符串的全排列
输入一个字符串，打印出该字符串中字符串的所有排列，例如，输入字符串"abc"，则输出由字符'a' 'b' 'c'所能排列出来的所有字符串"abc" "acb" "bac" "bca" "cab" "cba"
//Author:jeffmony@163.com
public class StringTest {
public static void main(String[] args) {
Solution instance = new Solution();
String string = "abcd";
char[] array = string.toCharArray();
for(int i=0;i<array.length;i++) {
System.out.print(array[i]);
}
System.out.println();
boolean result = instance.solution(array);
do {
for(int i=0;i<array.length;i++) {
System.out.print(array[i]);
}
System.out.println();
}while(instance.solution(array));
}
}
class Solution {
public boolean solution(char[] array) {
int i;
int length = array.length;
for(i=length-2;(i>=0)&&(array[i]>=array[i+1]);i--);
if(i<0)return false;
// System.out.println("i="+i);
int k;
for(k=length-1;(k>=i)&&(array[k]<=array[i]);k--);
// System.out.println("k="+k);
swap(array,i,k);
reverse(array, i+1,length-1);
return true;
}
public void swap(char[] array, int i, int j) {
char temp = array[i];
array[i]=array[j];
array[j]=temp;
}
public void reverse(char[] array, int start, int end) {
while(start<end){
char temp = array[start];
array[start]=array[end];
array[end]=temp;
start++;
end--;
}
}
}
4.字符串转换成整数
输入一个由数字组成的字符串，请把它转换成整数并输出。例如，输入的字符串"123"，输出整数123
5.回文判断
给定一个字符串，如何判断这个字符串是否是回文串，所谓的回文串，就是正反读都是一样的字符串。
//Author:jeffmony@163.com
public class StringTest {
public static void main(String[] args) {
Solution instance = new Solution();
String string = "madam";
char[] src = string.toCharArray();
boolean result = instance.solution(src);
System.out.println("result = " + result);
}
}
class Solution {
public boolean solution(char[] src) {
if (src.length <1) {
return false;
}
int start = 0;
int end = src.length-1;
while(start<end) {
if (src[start] != src[end]){
return false;
}
start++;
end--;
}
return true;
}
}
延伸拓展：如何判断一个链表是否是一个回文链表。
提示：用一个快慢指针来确定一下链表的中间位置，然后将后半部分链表逆序，和前半部分链表比较判断是否是回文链表。
6.最长回文子串
给定一个字符串，求它的最长回文子串的长度。
解法一：Manacher匹配算法
下面是完整的源码，具体的解法思路是：
//Author:jeffmony@163.com
public class StringTest {
public static void main(String[] args) {
Solution instance = new Solution();
String string = "12212321";
String result = instance.solution(string);
System.out.println("result = " + result);
}
}
class Solution {
public String solution(String s) {
String result = "$#";
for(int i=0;i<s.length();i++){
result += s.charAt(i);
result +="#";
}
int[] p = new int[result.length()];
for(int i=0;i<p.length;i++) {
p[i] = 0;
}
int mx = 0;
int id = 0;
int index=0;
int maxLen=0;
for(int i=1;i<result.length();i++){
p[i] = i <mx ? min(p[2*id-i],mx-i):1;
//判断数组是否越界
while(i+p[i] < result.length() && i-p[i]>0
&& result.charAt(i+p[i])==result.charAt(i-p[i])) {
p[i]++;
}
if(i+p[i] >mx) {
id=i;
mx=i+p[i];
}
if (p[i]-1>maxLen){
maxLen= p[i]-1;
index=i;
}
}
index=index/2-1;
return s.substring(index-maxLen/2, index+maxLen/2+1);
}
public int min(int a, int b) {
return a > b ? b:a;
}
}
