【算法题型总结】--5、字符串

public int getLongestPalindrome(String A, int n) {
          
          // 第 i 个字符到第 j 个字符是否是回文串
          boolean[][] dp = new boolean[n][n];
          int max = 0;
          // 字符串首尾字母长度差 (d = j-i)
          for (int d = 0; d < n; d++) {
              // 字符串起始位置 i
            for (int i = 0; i < n-d; i++) {
                // 字符串结束位置 j
                int j = i+d;
                // 如果字符串 i 到 j 的首尾相等，再根据字符串 i-1 到 j-1 来确定，即得到递推公式
                if(A.charAt(i) == A.charAt(j)) {
                    if(d == 0 || d == 1) {
                        dp[i][j] = true;
                    } else {
                        dp[i][j] = dp[i+1][j-1];
                    }
                    if(dp[i][j]) {
                        // 更新最大长度
                        max = Math.max(max, d+1);
                    }
                }
            }
        }
          return max;
    }

import java.util.*;
 
public class Solution {
    //判断回文的函数
    public boolean isHuiWen(String A, int n){
        int k = n / 2;
        for (int i = 0; i < k; ++i)
        {
            if (A.charAt(i) != A.charAt(n-1-i))
                return false;
        }
        return true;
    }
    public int getLongestPalindrome(String A, int n) {
        int maxlen=0;
        for(int i=0 ;i< n ;i++){
            for(int j=i+1 ;j<=n ;j++){
                //两层循环遍历出所有的子串，并且逐一判断是否是回文
                if(isHuiWen(A.substring(i, j),j-i)){
                    if(j-i>maxlen)
                        maxlen=j-i;
                }
            }
        }
        return maxlen;
    }
}

import java.util.*;
 
public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 计算两个数之和
     * @param s string字符串 表示第一个整数
     * @param t string字符串 表示第二个整数
     * @return string字符串
     */
    public String solve (String s, String t) {
        // write code here
        StringBuilder s1=new StringBuilder(s);
        StringBuilder s2=new StringBuilder(t);
        StringBuilder res=new StringBuilder();
        s1=s1.reverse();
        s2=s2.reverse();
        int x=0;
        int i=0;
        int j=0;
        while(i<s1.length() || j<s2.length() || x!=0){
            int sum=x;
            if(i<s1.length() && j<s2.length()){
                sum+=(s1.charAt(i++)-‘0‘)+(s2.charAt(j++)-‘0‘);
            }else if(i<s1.length() && j>=s2.length()){
                sum+=(s1.charAt(i++)-‘0‘);
            }else if(i>=s1.length() && j<s2.length()){
                sum+=(s2.charAt(j++)-‘0‘);
            }else{
                res.append(sum%10);
                break;
            }
            res.append(sum%10);
            x=sum/10;
        }
        return res.reverse().toString();
    }
}

import java.util.*;
public class Solution {
    /**
     *
     * @param strs string字符串一维数组
     * @return string字符串
     */
    public String longestCommonPrefix (String[] strs) {
        // write code here
        if(strs == null || strs.length == 0) return "";
 
        if(strs.length == 1) return strs[0];//strs只有一个元素的话直接返回
 
        //方法一：逐个比对法
/*
        int minLength = strs[0].length();
 
        for(String str : strs){//得到数组元素中长度最短的字符串对应的长度
            minLength = Math.min(minLength,str.length());
        }
 
        StringBuilder result = new StringBuilder();
 
        loop:for(int i = 0; i < minLength; i++){//遍历strs数组每个元素的每个字符
            for(int j = 1; j < strs.length; j++){//遍历strs数组每个元素
                if(strs[0].charAt(i) != strs[j].charAt(i)){
                    break loop;
                }
            }
            result.append(strs[0].charAt(i));
 
        }
        return result.toString();
*/
 
///*
        //方法二：调用startsWith方法
        String res = strs[0];
 
        for(int i = 1; i < strs.length; i++){
            while(!res.equals("") && !strs[i].startsWith(res)){
                res = res.substring(0,res.length() - 1);
            }
            if(res.equals("")) break;
        }
        return res;
//*/
    }
}

import java.util.*;
public class Solution {
    public boolean isValid (String s) {
        Stack<Character> stack = new Stack<Character>();
        char[] arr = s.toCharArray();
        int len = arr.length;
        for(int i=0;i<len;i++){
            if(arr[i]==‘(‘){
                stack.push(‘)‘);
            }else if(arr[i]==‘{‘){
                stack.push(‘}‘);
            }else if(arr[i]==‘[‘){
                stack.push(‘]‘);
            }else if(stack.isEmpty()||stack.pop()!=arr[i]){
                return false;
            }
        }
        return stack.isEmpty();
    }
}

import java.util.*;
 
public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 计算模板串S在文本串T中出现了多少次
     * @param S string字符串 模板串
     * @param T string字符串 文本串
     * @return int整型
     */
    public int kmp (String S, String T) {
        char[] t = T.toCharArray(), p = S.toCharArray();
        int i1 = 0, i2 = 0, res = 0;
        int[] next = next(p);
        while(i1 < t.length && i2 < p.length){
            if(t[i1] == p[i2]){
                i1 ++;
                i2 ++;
            }else if(next[i2] == -1){
                i1 ++;
            }else {
                i2 = next[i2];
            }
            if(i2 == p.length){
                res ++;
                i2 = next[i2-1];
                i1 --;
            }
        }
        if(i2 == p.length){
             
        }
        return res;
         
    }
     
     
    int[] next(char[] p){
        if(p.length == 1){
            return new int[]{-1};
        }
        int[] next = new int[p.length];
        next[0] = -1;
        next[1] = 0;
        //cn 表示next[i-1]
        int i = 2, cn = 0;
        while(i < p.length){
            if(p[i - 1] == p[cn] ){
                next[i ++] = ++cn;
            }else if(cn > 0){
                cn = next[cn];
            }else {
                next[i++] = 0;
            }
        }
        return next;
         
    }
}

public class Solution {
    public int kmp (String S, String T) {
        // write code here
         int result=0;
         for(int i=0;i<T.length();i++) { 
         int ff=i+S.length();
         if(ff<=T.length()) {
         String fsString= T.substring(i, ff);
         if(S.equals(fsString)) {
            result++; 
         }
        }
    }
         return result;
    }
}

import java.util.*;
 
public class Solution {
 
    public int longestValidParentheses (String s) {
        Stack<Integer> stack = new Stack<>(); // 设定栈，存储左括号
        stack.push(-1); // 压入-1，处理边界问题
        int res = 0; // 结果存储变量
         
        for (int i = 0;i < s.length();i++) {
            // 如果是左括号则直接入栈
            if (s.charAt(i) == ‘(‘) {
                stack.push(i);
            }else {
                // 如果是右括号，则弹栈
                stack.pop();
                // 判空，若栈为空，则说明i左侧已经没有可用的左括号，此时将i压入栈中，防止空栈异常
                if (stack.isEmpty()) {
                    stack.push(i);
                }else {
                    // 长度计算时无需加1，因为预先弹栈，相当于已经加过1，且在01边界上因为初始化时压入-1进栈，因此也得以解决
                    res = Math.max(res, i - stack.peek());
                }
            }
        }
         
        return res;
    }
}

import java.util.HashMap;
import java.util.Map;
public class Solution {
    public int FirstNotRepeatingChar(String str) {
        char [] tmp = new char[128];
        for(int i = 0;i<str.length();i++){
            char c = str.charAt(i);
            tmp[c]++;
        }
        for(int i = 0;i<str.length();i++){
            if(tmp[str.charAt(i)] == 1){
                return i;
            }
        }
        return -1;
    }
}

public class Solution {
    public int FirstNotRepeatingChar(String str) {
        if(str.length()==1) return 0;
        for(int i=0;i<str.length();i++){
           String s=str.substring(0,i)+str.substring(i+1);//获取不包含第i个字符的字符
            if(s.contains(str.charAt(i)+"")) continue;
            return i;
        }
        return -1;
    }
}

import java.util.*;
 
public class Solution {
    /**
     * 
     * @param str string字符串 
     * @return int整型
     */
    public int atoi (String str) {
        // write code here
        long n=0;
        int j=0;
       if(str==""||str.length()<1)
           return 0;
        for(int i=0;i<str.length();i++){
            if(str.charAt(i)==‘-‘){
                j=1;
                continue;
            }
             if(str.charAt(i)==‘+‘||str.charAt(i)==‘-‘||str.charAt(i)==‘ ‘){
                continue;
             }else if(str.charAt(i)<‘0‘||str.charAt(i)>‘9‘){
                 break;
             }else
            n=n*10+str.charAt(i)-‘0‘;
        }
        if(j==1){
            long k;
            k=n;
            n=0-k;
        }
        if(n>Integer.MAX_VALUE){
            return Integer.MAX_VALUE;
        }else if(n<Integer.MIN_VALUE){
            return Integer.MIN_VALUE;
        }
        return (int)n;
    }
}

import java.util.*;
public class Solution {
    ArrayList<String> res = new ArrayList<>();
    StringBuilder sb = new StringBuilder();
     
    public ArrayList<String> Permutation(String str) {
        //回溯
        char[] cs = str.toCharArray();
        boolean[] used = new boolean[cs.length];
        Arrays.sort(cs);
        backtrack(cs, used, 0);
        return res;
    }
     
    public void backtrack(char[] cs, boolean[] used, int start) {
        if (sb.length() == cs.length) {
            res.add(sb.toString());
            return;
        }
        for (int i = 0; i < cs.length; i++) {
            if (i > 0 && cs[i] == cs[i - 1] && !used[i - 1]) continue; //重复的要进行排序
            if (!used[i]) {
                used[i] = true;
                sb.append(cs[i]);
                backtrack(cs, used, i + 1);
                used[i] = false;
                sb.setLength(sb.length() - 1); // 也可以是path.deleteCharAt(path.length()-1);  ？？？？？？？？？？？？？？？             
            }
        }
    }
}

public String solve (String IP) {
        // write code here
    String[] c = IP.split("\\.");
    if(c.length != 4) {
        c = IP.split(":");
        if(c.length != 8) {
            return "Neither";
        } else {
            String regex="^[A-Fa-f0-9]+$";
            for(int i = 0; i < 8; i++) {
                String s = c[i];
                if(s.length() > 4 || !s.matches(regex)) {
                    return "Neither";
                }
            }
            return "IPv6";
        }
    } else {
        for(int i = 0; i < 4; i++) {
            String s = c[i];
            int num = Integer.parseInt(s);
            if(num > 255 || (c[i].charAt(0) == ‘0‘ && num > 0)) {
                return "Neither";
            }
        }
        return "IPv4";
    }
}