美文网首页
字符串问题合集

字符串问题合集

作者: 正经龙 | 来源:发表于2019-08-13 17:21 被阅读0次

    1. 验证回文串

    题目描述: 输入一个字符串,只关注字母和数字,判断字符串是否为回文串。空字符串也可以认为是回文串


    image.png

    解题思路
    关键函数: Character.isLetterOrDigit()判断字符是否为数字或字母
    " ".toLowerCase()将字符串中的大写字母全部变为小写字母

    1. 设置前后两个坐标值 i 和 j
    2. 先判断是否为字母和数字
      如果不是 i++ 或者 j--
    3. 如果是,则判断两者是否相等,不相等直接返回false;
    4. 如若全部相等则返回true;
        public boolean isPalindrome(String s) {
            if(s.length() == 0)
                return true;
            int len = s.length();
            int i = 0;
            int j = len - 1;
            while(i<j&&i<len&&j>=0){
                while(!Character.isLetterOrDigit(s.charAt(i))&&i<j){
                    i++;
                }
                while(!Character.isLetterOrDigit(s.charAt(j))&&i<j){
                    j--;
                }
                if(!s.substring(i,i+1).toLowerCase().equals(s.substring(j,j+1).toLowerCase())&&i<j){
                    return false;
                }
                i++;
                j--;
            }
            return true;
        }
    

    分割回文串

    题目描述:


    image.png

    解题思路:

    1. 从0-i进行判断,如果0-j为回文串,则压入0-j,继续判断j-i是否为回文串
    2. 直到判断到最后一个字符,就将生成的新的分割方法存入result中
        List<List<String>> result = new ArrayList<>();
        String s;//对象变量,方便存储
        public List<List<String>> partition(String s) {
            if(s.length()==0)
                return result;
            this.s = s;//存储对象变量
            function(0,new ArrayList<>());
            return result;
            
        }
        public boolean isValid(int begin,int end){
            while(begin < end){
                if(this.s.charAt(begin) != this.s.charAt(end))
                    return false;
                begin++;
                end--;
            }
            return true;
        }
        public void function(int index,List<String> list){
            if(index > (s.length()-1))
            {
                //一次排序完成
                this.result.add(new ArrayList<>(list));
            }
            
            for(int i = index; i < s.length();i++){
                if(isValid(index,i)){
                    list.add(this.s.substring(index,i+1));
                    function(i+1,list);
                    list.remove(list.size()-1);
                }
            }
        }
    

    3. 单词拆分

    题目描述:


    image.png
    image.png
    public boolean wordBreak(String s, List<String> wordDict) {
            //动态规划的解法
            if(s == null || s.length() == 0)
                return true;
            boolean res[] = new boolean[s.length()+1];//res[i]代表了从1-i个字符可以用字典中的词来填充
            
            res[0] = true;//第0个默认为true
            
            for(int i = 0; i < s.length();i++){
                StringBuilder builder = new StringBuilder(s.substring(0,i+1));//从下标为0到下标为i的字符串,也就是第i+1个字符
                for(int j = 0; j<=i;j++){
                    if(res[j]&&wordDict.contains(builder.toString())){
                        res[i+1] = true;
                        //这里的第res[i+1]代表了前i 个字符可以用字典中的单词代替
                        //第1-j个字符为true,同时j+1到i+1的字符串在字典里面;
                        break;
                    }
                    builder.deleteCharAt(0);//删除前j个字符
                }
            }
            
            return res[s.length()];
                
        }
    

    4. 单词拆分Ⅱ

    题目描述:


    image.png 示例

    思路:
    动态规划,每次截取字符串前方一部分字符串,判断字典中是否存在。
    如果存在,则记录当前单词,并继续判断之后的字符

    v1.0实现代码
    class Solution {
        List<String> result;
        String s;
        public List<String> wordBreak(String s, List<String> wordDict) {
            result = new ArrayList<>();
            this.s = s;//创建返回值和保存字符串常量
            cutWords(0,wordDict,new ArrayList<>());
            return result;
        }
        
        public void cutWords(int index,List<String> wordDict,List<String> save){
            /**
            *
            参数说明,index表示还未处理的最前下标,wordDice字典,save暂时保存的数据
            */
            if(index >= s.length()){
                //已经找到了个划分方法
                StringBuilder builder = new StringBuilder();
                for(int i = 0; i < save.size()-1;i++){
                    builder.append(save.get(i));
                    builder.append(" ");
                }
                builder.append(save.get(save.size()-1));//最后一个单词
                result.add(builder.toString());
            }
            else{
                for(int i = index;i < s.length();i++){
                    StringBuilder builder = new StringBuilder(s.substring(index,i+1));
                    if(wordDict.contains(builder.toString())){
                        save.add(builder.toString());
                        cutWords(i+1,wordDict,save);
                        save.remove(save.size()-1);
                    }
                }    
            }
          
        }
    }
    

    出现的问题: 在某些用例中会出现超时的错误


    超时

    这就要用到剪枝,在进行动态规划之前,首先判断当前是否能够进行单词划分

    v 2.0
    class Solution {
        List<String> result;
        String s;
        public List<String> wordBreak(String s, List<String> wordDict) {
            result = new ArrayList<>();
            this.s = s;//创建返回值和保存字符串常量
    
            //加入剪枝
            boolean []judge = new boolean[s.length()+1];
            judge[0] = true;
            for(int i = 0; i < s.length();i++){
                for(int j = 0; j <= i;j++){
                    if(judge[j]&&wordDict.contains(s.substring(j,i+1))){
                        judge[i+1] = true;
                        break;
                    }
                }
            }
            if(!judge[s.length()]){
                return result;
            }
            cutWords(0,wordDict,new ArrayList<>());
            return result;
        }
        
        public void cutWords(int index,List<String> wordDict,List<String> save){
            /**
            *
            参数说明,index表示还未处理的最前下标,wordDice字典,save暂时保存的数据
            */
            if(index >= s.length()){
                //已经找到了个划分方法
                StringBuilder builder = new StringBuilder();
                for(int i = 0; i < save.size()-1;i++){
                    builder.append(save.get(i));
                    builder.append(" ");
                }
                builder.append(save.get(save.size()-1));//最后一个单词
                result.add(builder.toString());
            }
            else{
                for(int i = index;i < s.length();i++){
                    StringBuilder builder = new StringBuilder(s.substring(index,i+1));
                    if(wordDict.contains(builder.toString())){
                        save.add(builder.toString());
                        cutWords(i+1,wordDict,save);
                        save.remove(save.size()-1);
                    }
                }    
            }
            
        }
    }
    

    总结

    对于字符串的题目,要记录的是几个关键的函数与ASCII码范围

    1. 变大小写的函数
    "".toLowerCase();   //字符串变小写
    "".toUpperCase();   //字符串变大写
    
    1. 判断是否是字母或数字
    ''.isLetter();  //判断是否是字母
    ''.isDigit();    //判断是否是数字
    ''.isLetterOrDigit();//判断是否是数字或字母
    
    1. 字符串和字符数组之间的相互转换
            String str = "";
            str.toCharArray();   //String 转化为char数组
    
    1. ASCII码
    大写字母: 'A'   65
    小写字母:'a'  97
    数字:'0'  48
    

    相关文章

      网友评论

          本文标题:字符串问题合集

          本文链接:https://www.haomeiwen.com/subject/djmvjctx.html