精华内容
下载资源
问答
  • 【子串查找】在字符串中找出子串第一次出现的位置,所有出现的位置(次数),是否包含子串


    📚题目一:子串第一次出现的位置

    给定两个字符串str1和str2,找到str2在str1第一次出现的位置。

    str1 = "aefbbcabc"
    str2 = "bc"
    输出 >>> 4
    
    str1 = "bcbcbc"
    str2 = "bc"
    输出 >>> 0
    

    👊思考:如果是统计子串所有出现的下标呢?

    1. 调用API,String的indexOf方法

    【indexOf解决战斗】

    public static int indexOfStr_I(String str, String sub) {
    	return str.indexOf(sub);
    }
    

    2. 截取目标串的长度进行匹配

    【思路】

    从str1中截取和str2长度一样的字符串,和str2比较,相等即找到,不相等再截取一个新的字符串,直到找到或找不到

    public static int findSubString_II(String str1, String str2) {
        int offset = 0;
        String substr = null;
        if ((str1 == null) || (str2 == null) || (str1.length() < str2.length())) {
            return -1;
        } else {
            while (offset <= (str1.length() - str2.length())) {
                //String.copyValueOf(要复制的字符数组, 开始索引, 复制长度)
                substr = String.copyValueOf(str1.toCharArray(), offset, str2.length());
                if (substr.equals(str2)) {
                    return offset;
                }
                offset++;
            }
            return -1;
        }
    }
    

    🔗Java String copyValueOf方法

    3. 滑动窗口

    【思路】

    在str1中找str2中第一个字符出现的位置,然后再一个字符一个字符的比较str1和str2,如果到str2结束都相等,则找到str2在str1中第一次出现的位置。否则再在str1中找str2的第一字符出现的位置

    public static int slideToSubString_III(String str, String sub) {
        int i = 0, j = 0;
        int index = 0;
        while (i < str.length() && j < sub.length()) {
            if (str.charAt(i) == sub.charAt(j)) {
                i++;
                j++;
            } else {
                i = i - j + 1;
                j = 0;
            }
            if (j == sub.length()) {
                return i - j;
            }
        }
        return 0;
    }
    


    🎈题目二:子串出现的位置(次数)

    测试用例

    输入 >>>
    源字符串:String str = "www.baidu.com/www.sina.com---www";
    
    目标字符串:String sub = "www";
    
    输出 >>> 3, [0, 14, 29]
    

    1. indexOf方法

    使用String类的indexOf方法,每次找到第一次出现的子串后,改变起始寻找位置

    lastIndexOf是从后往前找

    public static void checkI(String str, String subStr) {
        int index = 0, count = 0;
        List<Integer> list = new ArrayList<>();
        while (index <= str.length()) {
            index = str.indexOf(subStr, index);
            if (index == -1) {
                break;
            }
            list.add(index);
            index += 1;
            count++;
        }
        System.out.println(list);
        System.out.println(count);
    }
    

    2. split根据子串分割字符数组,统计子串出现次数

    【思路】: 通过str.split(subStr),将子串放入到字符串数组中,返回数组长度即可

    无法记录出现位置

    • 使用子串来切割父串,根据结果数组长度获取次数
    • 考虑特殊情况–> 子串在末尾,要给截取结果数组长度加1
    public static void checkII(String str, String subStr) {
        int count = 0;
        String[] arr = str.split(subStr);
        int len = arr.length;
        if (str.endsWith(subStr)) {
            //如果子串在末尾
            len++;
        }
        count = len - 1;
        System.out.println(count);
    }
    

    3. 字符串切割,统计子串出现次数

    【思路】: indexOf方法记录子串存现的位置,类比方法一

    无法记录出现位置

    public static void checkIII(String str, String subStr) {
        // 定义计数器
        int count = 0;
        // 定义变量,保存indexOf查找后的结构
        int index = 0;
        // 开始循环找,条件,indexOf == -1字符串没有了
        // 先用str.indexOf(key)找索引赋值给index,如果index=-1,则说明有字符串
        while ((index = str.indexOf(subStr)) != -1) {
            count++;
            //获取索引,和字符串长度求和,截取字符串
            str = str.substring(index + subStr.length());
        }
        System.out.println(count);
    }
    

    4. 正则表达式,统计子串出现次数

    public static void checkIV(String str, String subStr) {
        int count = 0;
        Pattern pattern = Pattern.compile(subStr);
        Matcher matcher = pattern.matcher(str);
        while (matcher.find()) {
            count++;
            //group方法返回由以前匹配操作所匹配的输入子序列
            System.out.println("匹配项" + count + ":" + matcher.group());
        }
        System.out.println("匹配个数为" + count);
    }
    


    🍳题目三:是否包含子串

    最高效的方式,使用contains方法

    源串.contains(子串)

    • 【方法二】通过 substring() 方法对长字符串a进行截取,然后依次和b字符串进行比较,相同就返回true并且跳出,不相同就移位继续比较

    🔗其他方法参考


    📌题目四:是否包含子串中的所有字符(无序, 包含即可)

    问题:

    比较两个字符串A和B,确定A中是否包含B中所有的字符。字符串A和B中的字符都是 大写字母。

    • 给出 A = “ABCD” B = “ACD”,返回 true
    • 给出 A = “ABCD” B = “AABC”, 返回 false

    注意事项:

    在 A 中出现的 B 字符串里的字符不需要连续或者有序。


    【分析】

    实质上利用的是哈希表的思想。只有大写字母,一共26个,遍历A的时候,往里面压,遍历B的时候,往外边弹,如果不够弹,则不包含。

    1. 计数排序思想

    利用下标偏移量,数组元素统计出现次数(计数排序思想),index[i]小于0则不包含

    public static boolean containsCharacterI(String str, String subStr) {
        int[] index = new int[26];
        for (int i = 0; i < str.length(); i++) {
            index[str.charAt(i) - 'A']++;
        }
        for (int i = 0; i < subStr.length(); i++) {
            index[subStr.charAt(i) - 'A']--;
            if (index[subStr.charAt(i) - 'A'] < 0) {
                return false;
            }
        }
        return true;
    }
    

    2. HashMap

    • 先将26个字母放入keyvalue全部为0
    • 统计源串的字母频率++
    • 子串字母--
    • 出现 value < 0,则不包含
    public static boolean containsCharacterII(String str, String subStr) {
        Map<Character, Integer> map = new HashMap<>();
        // 放入26个大写字母
        for (int i = 0; i < 26; i++) {
            map.put((char) (i + 65), 0);
        }
        // 字符统计
        for (int i = 0; i < str.length(); i++) {
            Character key = str.charAt(i);
            map.put(str.charAt(i), map.get(key) + 1);
        }
        for (int i = 0; i < subStr.length(); i++) {
            Character key = subStr.charAt(i);
            if (map.containsKey(key)) {
                map.put(key, map.get(key) - 1);
            }
            if (map.get(key) < 0) return false;
        }
        return true;
    }
    
    展开全文
  • 找到字符串中的最长回文子串Problem statement: 问题陈述: Given a string you have to find out the longest ... 给定一个字符串,您必须给定的字符串中找出最长的回文子序列。 Input: T Test case ...

    找到字符串中的最长回文子串

    Problem statement:

    问题陈述:

    Given a string you have to find out the longest palindromic subsequence from the given string.

    给定一个字符串,您必须从给定的字符串中找出最长的回文子序列。

        Input:
        T Test case
        T no of input string will be given to you.
    
        E.g.
        3
        
        bghaufahgt
        souabbuos
        sahajkhahas
        
        Constrain 
        1≤ length (string) ≤100
        
        Output:
        Print the longest palindromic subsequence from that string
    
    

    Example

        T=3
    
        Input:
        bghaufahgt
        
        Output:
        ghafahg
        
        Input:
        souabbuos
        
        Output:
        soubbuos
        
        Input:
        sahajkhahas
        
        Output:
        sahajahas
    
    

    Explanation with example:

    举例说明:

    Let there is a string str.

    让我们有一个字符串str 。

    Now possible arrangements are:

    现在可能的安排是:

    1. Single middle characters like aba

      像aba这样的单个中间字符

    2. Paired middle characters like bb

      配对的中间字符,如bb

    Let, f(a,b) = length of palindromic substring from index a to index b.

    令f(a,b)=从索引a到索引b的回文子串的长度 。

    Considering the above three facts:

    考虑以上三个事实:

    1. If there is only one character then f(a,a) = 1

      如果只有一个字符,则f(a,a)= 1

    2. If there are two characters a and a+1 both are same then f(a,a+1) = 2 if both are not same then f(a,a+1) = 1.

      如果两个字符a和a + 1都相同,则f(a,a + 1)= 2;如果两个字符不相同,则f(a,a + 1)= 1 。

    3. If there is a substring starting from index a to index b then,

      如果存在从索引a到索引b的子字符串,

      1. If str[a] and str[b] both are same then f(a,b) = f(a+1,b-1) + 2
      2. 如果str [a]和str [b]都相同,则f(a,b)= f(a + 1,b-1)+ 2
      3. If str[a] and str[b] both are not same then f(a,b)= max{ f(a+1,b) , f(a,b-1) }
      4. 如果str [a]和str [b]都不相同,则f(a,b)= max {f(a + 1,b),f(a,b-1)}

    For, str = bghaufahgt

    因为, str = bghaufahgt

    Find out the longest palindromic subsequence from a string

    To find out the characters in the palindrome we will follow this approach:

    为了找出回文中的字符,我们将采用以下方法:

    1. The max length will be the top right block.

      最大长度将在右上角。

    2. Every time we will check the left and bottom adjacent blocks.

      每次我们将检查左侧和底部相邻的块。

      1. If both the blocks contain the same value then we will go for any of them.
      2. If any block contains a value such that the difference between the current value and the value at the block is 2 then we will go for that block and make a note of that character present in the string whose index is the same as the column number.
      3. When we will get the value equals to 1 then stop the traversal.
    Find out the longest palindromic subsequence from a string

    C++ Implementation:

    C ++实现:

    #include <bits/stdc++.h>
    using namespace std;
    
    int arr[101][101];
    
    void print_palindrome(string str)
    {
        int len = str.length();
        int i = 0;
        int j = len - 1;
        int num = arr[i][j];
        vector<char> v;
        int flag = 0;
        while (i < len && j >= 0) {
            if (num == 2) {
                flag = 1;
                break;
            }
            if (num == 1)
                break;
            //if the left block has the value by which
            //the difference will be 2
            if (arr[i][j - 1] + 2 == num) {
                v.push_back(str[j]);
                j--;
                num = arr[i][j];
                if (num == 1 || num == 2) {
                    v.push_back(str[j]);
                }
            }
            //if the bottam block has the value by
            //which the difference will be 2
            if (arr[i + 1][j] + 2 == num) {
                v.push_back(str[i]);
                i++;
                num = arr[i][j];
                if (num == 1 || num == 2) {
                    v.push_back(str[i]);
                }
            }
            if (arr[i][j - 1] == num) {
                j--;
            }
            else {
                i++;
            }
        }
        for (int i = 0; i < v.size(); i++) {
            cout << v[i];
        }
        //cout<<endl;
        for (int i = v.size() - 1; i >= 0; i--) {
            if (flag && i == v.size() - 1) {
                cout << v[i];
            }
            else if (i != v.size() - 1) {
                cout << v[i];
            }
        }
        cout << endl;
    }
    
    void length_of_palindrom(string str)
    {
        int len = str.length();
        memset(arr, 0, sizeof(arr));
        for (int i = 0; i < len; i++) {
            arr[i][i] = 1;
        }
        for (int i = 0; i < len - 1; i++) {
            if (str[i] == str[i + 1])
                arr[i][i + 1] = 2;
            else
                arr[i][i + 1] = 1;
        }
        for (int l = 3; l <= len; l++) {
            for (int i = 0; i <= len - l; i++) {
                int j = i + l - 1;
                if (str[i] == str[j])
                    arr[i][j] = arr[i + 1][j - 1] + 2;
                else
                    arr[i][j] = max(arr[i + 1][j], arr[i][j - 1]);
            }
        }
        cout << "Palindrome : ";
        print_palindrome(str);
        cout << endl;
        return;
    }
    
    int main()
    {
        int t;
        cout << "Test Case : ";
        cin >> t;
        while (t--) {
            cout << "Enter the string : ";
            string str;
            cin >> str;
            length_of_palindrom(str);
        }
    }
    
    

    Output

    输出量

    Test Case : 3
    Enter the string : bghaufahgt
    Palindrome : ghafahg
    
    Enter the string : souabbuos
    Palindrome : soubbuos
    
    Enter the string : sahajkhahas
    Palindrome :  sahajahas
    
    
    

    翻译自: https://www.includehelp.com/icp/find-out-the-longest-palindromic-subsequence-from-a-string.aspx

    找到字符串中的最长回文子串

    展开全文
  • 题目给定一个字符串找出字符串的最长回文子串。回文字符串指的就是左右两边看都一样的字符串,如aba,cddc都是回文字符串字符串abbacdc存在的回文子串有abba和cdc,因此它的最长回文子串为abba。代码public ...

    题目

    给定一个字符串,找出该字符串的最长回文子串。回文字符串指的就是从左右两边看都一样的字符串,如aba,cddc都是回文字符串。字符串abbacdc存在的回文子串有abba和cdc,因此它的最长回文子串为abba。

    代码

    public class LongPalindromic {
    
        public static void main(String[] args) {
    
            String str = "abcddccad";
            String result = getPalindromic(str);
            System.out.println(result);
        }
    
        private static String getPalindromic(String str) {
    
            char[] ch = str.toCharArray();
            String post = "";
            String result = "";
            //当回文字符串的长度为基数时
            for (int i = 0; i < ch.length; i++) {
                post = getSubstring(ch, i, i);
                if (post.length() > result.length()) {
                    result = post;
                }
            }
            //当回文字符串的长度为偶数时
            for (int i = 0; i < ch.length; i++) {
                post = getSubstring(ch, i, i + 1);
                if (post.length() > result.length()) {
                    result = post;
                }
            }
    
            return result;
        }
    
        private static String getSubstring(char[] ch, int i, int j) {
    
            //从指定位置向两边移动来判断是否满足回文数
            while(i >= 0 && j <= ch.length - 1 &&  ch[i] == ch[j]){
                i--;
                j++;
            }
    
            //当不满足条件的时候将不满足循环条件的上一个状态的字符串返回
            return String.valueOf(ch).substring(i + 1, j);
            //substring()方法方法用于提取字符串中介于两个指定下标之间的字符
            //当substring(2,3)返回位置为2下表的字符。
        }
    
    }
    展开全文
  • 找出两个字符串中最大相同的子串 public class StringMaxString { //找一个字符串的最大子串 public static void main(String[] args) { // TODO Auto-generated method stub String s1=





    // 找一个字符串的最大子串
    	public static void main(String[] args) {
    
    		String s1 = "qwerabcdtyuiop";
    		String s2 = "xcabcdvbn";
    		String stringMax = stringMax(s1, s2);
    		System.out.println("最大的相同子字符串是:" + stringMax);
    	}
    
    	/**
    	 * 找出两个字符串中最大的相同子字符串
    	 * 
    	 * @param s1
    	 * @param s2
    	 * @return
    	 */
    	private static String stringMax(String s1, String s2) {
    		// 记录相同子字符串
    		String sameString = null;
    		// 比较两个字条串的长度,这里是设置S1的长度大于S2的长度
    		if (s1.length() < s2.length()) {
    			// 如果s2的长度大,那么就将两个字符串进行替换
    			String temp = s1;
    			s1 = s2;
    			s2 = temp;
    		}
    		// 如果s2就被包含在s1中,那么这两个字符串最大的子串就是s2
    		boolean isContains = s1.contains(s2);
    
    		if (isContains) {
    			return s2;
    		} else {
    			boolean b1 = false;
    			// 如果s2不是两个字符串最大的子类,那么再进行循环查找
    			for (int i = 0; i < s2.length(); i++) {
    				for (int j = 0; j <= i; j++) {
    					// 获取每次进行比较的子字条串
    					String str = s2.substring(j, s2.length() - i + j);
    					System.out.println("第" + i + "次比较:" + str);
    					if (s1.contains(str)) {
    						sameString = str;
    						b1 = true;
    						break;
    					}
    
    				}
    				// 如果比较到s2中最小的为2的时候还没有相同的字符串,我们就默认没相同的子字符串
    				if (s2.substring(0, s2.length() - i).length() == 2) {
    					System.out.println("没有相同的子字符串");
    					b1 = true;
    					break;
    
    				}
    				if (b1 == true)
    					break;
    			}
    		}
    		return sameString;
    	}
    


    编译运行:



    分析原理图:






    String字符串处理详细说明:点击打开查看



    展开全文
  • 给定一个字符串 s,找到 s 最长的回文子串。你可以假设 s 的最大长度为 1000。 示例 1: 输入: “babad” 输出: “bab” 注意: “aba” 也是一个有效答案。 示例 2: 输入: “cbbd” 输出: “bb” 回文的特性:...
  • *获取字符串最长子串,为了避免回溯,采用一个数组指针,每个字符 *对应的值作为数组索引并指向该字符开始的子串;在遍历该字符串的 *过程,数组指针指向该字符最后一次出现的位置; *temp指向 字符*end 上一次在...
  • 找出字符串中最长的子串: ②外循环for(i = 0;i(p);i++) ,为什么这里不写for(i = 0;str[i]!='\0';i++)呢? 答:内循环判断最后一个子串的时候,i一直要自加到i=len,即p[len]='\0' 的时候,才退出内循环。 然后...
  • 代码:# 计算两个字符串的最长公共子串 def getNumofCommonSubstr(str1, str2): lstr1 = len(str1) lstr2 = len(str2) record = [[0 for i in range(lstr2 + 1)] for j in range(lstr1 + 1)] # 多一位,为了在...
  • 找出字符串中的最长子串,要求子串的所有字符相同。 例如:str ="sssddddabcdef" ,则输出字串为:dddd;例如:str ="ccdfff" 则输出字串为:fff。 char *GetSameSubStr(char *str) { assert(str!=NULL); ...
  • 主要介绍了java实现求两个字符串最大公共子串的方法,详细的描述了两个字符串的最大公共子串算法的实现,需要的朋友可以参考下
  • 通过编辑距离算法对两字符串相似度对比后顺序取出所有公共子串
  • 1. 获取两个字符串中最大相同子串

    千次阅读 2019-12-24 19:36:13
    需要找出这里两个字符串中最大的字符子串,这里就是**“ghj”**. 查找的方法就是把两个字符串中较短的那个依次减小,然后按照该长度在短的字符串中获取所有子串依次判断该子串是否存在于长的字符串中. 上面的方法听着...
  • [java] view plain copy print...// 一个字符串的最大子串 public static void main(String[] args) { String s1 = ”qwerabcdtyuiop”; String s2 = ”xcabcdvbn”; String stringMax = stringMa
  • 获取两个字符串中最大相同子串 思路 找到最大的相同子串是一个不断增加子串长度的过程 我们可以先一个字符开始,然后慢慢增加 找到最长的那个字符串就是最大相同子串 可以用String类的subString方法和contain...
  • 给定一个字符串找出字符串的最长回文子串。回文字符串指的就是左右两边看都一样的字符串,如aba,cddc都是回文字符串字符串abbacdc存在的回文子串有abba和cdc,因此它的最长回文子串为abba。 中心法求最长...
  • * @描述 获取两个字符串中相同的子串 * <p> * <p> * 思路 * 1.既然取得最大子串,先看短的那个字符串是否在长的字符串中 * 如果存在,短的那个字符串就是最大字符串 * 2.如果不是,那么就将短的...
  • 查找一个字符串中最大回文子串

    千次阅读 2019-04-23 10:37:08
    给定一个字符串,查找该字符串中的最大回文子串。 如: "a" 最大回文子串为 "a" 大小为1 "aa" 最大回文子串为"aa" 大小为2 "aaa" 最大回文子串为"aaa" 大小为3 "aba" 最大回文子串为"aba" 大小为3 ...
  •  给定一个字符串S=A1A2...An,要求找出其最长回文子串(Longest Palindromic Substring)。所谓回文子串就是S的某个子串Ai...Aj为回文。例如,对字符串S=abcdcbeba,它的回文子串有:bcdcb,cdc,beb,满足题目要求...
  • 找出两个字符串的最大公共子串

    千次阅读 2015-10-23 16:54:18
    找出两个字符串的最大公共子串。(如:abcdefg和abdefg的最大公共子串是defg)有人给出以下两种思路:1.以两个字符串c1c2为行列构成矩阵a,相同a[i][j]为1…最大就是斜方向连续1最多的(另一网友建议:如果2个字符串...
  • 找出字符串的最长不重复子串,输出长度和子串 方法一:穷举法,空间复杂度是O(1),时间复杂度是O(N^4) 方法二:贪心算法,时间复杂度O(N)
  • function getsymStr(str) { if(str.length === 1) { return str; } var result = []; var l = str.length; var defaultMostStr = '暂无对称子串'; var isSym = function (str)...
  • 主要介绍了C语言求两个字符串的最长公共子串,实例分析了C语言操作字符串的技巧,具有一定参考借鉴价值,需要的朋友可以参考下
  • 找出字符串中重复的子串,如输入abcab,输出a ab b。 核心代码如下: #include <iostream> #include <vector> #include <algorithm> #include <cstring> #include <string> #include ...
  • 给出一个字符串找出一个字符串的最长回文子串,比如输入:babad,输出:bab或aba,输入:dbbd,输出::bb 2、解题思路 (1)暴力求解 找出字符串的每个子串,时间复杂度为O(n^2),判断这个字符串是否为...
  • LeetCode有这么一道题:给定一个字符串 s,找到 s 最长的回文子串。你可以假设 s 的最大长度为1000。示例 1:输入: "babad"输出: "bab"注意: "aba"也是一个有效答案。示例 2...
  • 给定一个字符串和一个子串。子串中的字符可能重复,输出子串出现的次数。(Java实现) 2020酷家乐笔试原题: 用的是最简单的,暴力求解法。 package Day43; /** * @Author Zhongger * @Description 给定一个字符...
  • /** *查找一个字符串中的所有子串的位置 * * */ function searchSubStr(str: any, subStr: any, positions: any): void { let pos = str.indexOf(subStr); while (pos &g...
  • 删除字符串中指定的子串,并统计删除的字符串的个数 思路:首先使用String的trim()方法去掉String的空格,不改变字符串,然后使用String的indexOf方法找到要删除的子串的位置,再使用String的subString()方法...
  • 求两个字符串的最长公共子串

    万次阅读 多人点赞 2018-08-12 15:55:48
    问题:有两个字符串str和str2,求两个字符串中最长公共子串长度。 比如:str=acbcbcef,str2=abcbced,则str和str2的最长公共子串为bcbce,最长公共子串长度为5。 算法思路: 1、把两个字符串分别以行和列组成...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 54,508
精华内容 21,803
关键字:

从字符串中找出子串