leetcode之字符串相关

发表于

记录在算法学习过程中与字符串相关的题目，easy部分。

1002 Find Common Characters

题目描述

Given an array A of strings made only from lowercase letters, return a list of all characters that show up in all strings within the list (including duplicates). For example, if a character occurs 3 times in all strings but not 4 times, you need to include that character three times in the final answer.

You may return the answer in any order.

题目解析

寻找字符串中出现的相同字符，重复的字符按照重复的次数算。
每个字符串是等长的，以第一个字符串为标准对其他字符串进行字符查找，如果找到该字符，就删除该字符，因为被查找的字符中可能有重复的字符，计数器加1，若其他字符串都有这个字符，计数器的值为A.size()-1，最后判断计数器，直接将字符push_back进入res会报类型错误，可以用一个string类型的变量中转一下。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
public:
    vector<string> commonChars(vector<string>& A) {
        vector<string> res;
        string s;
        size_t npos = -1;
        int i,j,num=0;
        for(i=0;i<A[0].length();i++){
            for(j=1;j<A.size();j++){
                int pos = A[j].find_first_of(A[0][i]);
                if(pos != npos){
                    num += 1;
                    A[j].erase(pos,1);
                }
            }
            if(num==A.size()-1){
                s = A[0][i];
                res.push_back(s);
            }
            num = 0;
        }
        return res;
        
    }
};

557 Reverse Words in a String III

题目描述

Given a string, you need to reverse the order of characters in each word within a sentence while still preserving whitespace and initial word order.

Example 1:
Input: “Let’s take LeetCode contest”
Output: “s’teL ekat edoCteeL tsetnoc”
Note: In the string, each word is separated by single space and there will not be any extra space in the string.

题目解析

以空格为间隔，对字符串内的每个子串进行反转。
思路：以空格为间隔，取每个子串，然后对每个子串反转，然后连接。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class Solution {
public:
string reverseWords(string s){
    string res = "";
    int pre_space = -1;
    int space = 0;
    string str;
    while(space != -1){
        space = s.find(' ',space+1);
        str = s.substr(pre_space+1,space-pre_space-1);
        reverseWord(str);
        res += str;
        res += " ";
        pre_space = space;
    }
    res.erase(res.length()-1,1);
    return res;

}

void reverseWord(string &s){
    if(s.length()==0)
        return;
    char temp;
    int length = s.length();
    for(int i=0;i<length/2;i++){
        temp = s[i];
        s[i] = s[length-1-i];
        s[length-1-i] = temp;
    }
    return;
}
};

优化

看到一个排名靠前的解法，遍历字符串，以空格为间隔，如果遇到空格，则以倒序连接在res字符串中。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
public:
    string reverseWords(string s) {
        ios::sync_with_stdio(false);
        string ans="";
        string temp="";
        s+=' ';
        for(int i=0;i<s.length();i++){
            if(s[i]!=' ')
                temp+=s[i];
            else{
                
                for(int j=0;j<temp.length();j++){
                    ans+=temp[temp.length()-j-1];
                }
                if(i<s.length()-1)
                ans+=' ';
                temp="";
            }
        }
        
        
        
        return ans;
    }
};

821 Shortest Distance to a Character

题目描述

Given a string S and a character C, return an array of integers representing the shortest distance from the character C in the string.

1
2
3
Example 1:
Input: S = "loveleetcode", C = 'e'
Output: [3, 2, 1, 0, 1, 0, 0, 1, 2, 2, 1, 0]

题目解析

返回字符串中每一个位置距离给定字符的最小距离，给定字符C必定包含在字符串中，注意不是返回字符串中每个字符距离给定字符的最小距离。
我的方法是先找出C在字符串中的所有位置，然后再计算每一个位置与字符C的距离，取最小值。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
    vector<int> shortestToChar(string S, char C) {
        vector<int> dis(S.length(),S.length()+1);
        vector<int> pos;
        int first_idx = S.find(C,0);
        for(int i=0;i<S.length();i++){
            dis[i] = abs(i-first_idx);
            if(S[i] == C){
                pos.push_back(i);
                dis[i] = 0;
            }
        }

        for(int i=0;i<dis.size();i++){
            for(int j=1;j<pos.size();j++){
                if(dis[i] > abs(pos[j] - i))
                    dis[i] = abs(pos[j] - i);
            }
        }

        return dis;
    }
};

优化

优化：看了计算复杂度较低的解法，设返回值dis：
先遍历字符串，找出字符C的位置，对应位置的dis[i]=0；
再次遍历字符串，若遇到的是目标字符，则以该字符为界，分别向左右两边遍历，更新每个dis的最小值。count记录遍历的位置距离目标字符的距离，每次向左或向右移动时，count++。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
class Solution {
public:
    vector<int> shortestToChar(string S, char C) {
        int len = S.length();
        int count;
        vector<int> vec(len,20000);
        for(int i=0;i<len;i++)
        {
            if(S[i] == C)
                vec[i] = 0;
        }
        for(int i=0;i<len;i++)
        {
            if(vec[i] == 0)
            {
                count =1;
                for(int j = i-1;j>= 0 ;j--)
                {
                    if(vec[j] > count)
                        vec[j] = count;
                    count++;
                }
                count = 1;
                for(int j = i+1;j<len ;j++)
                {
                    if(vec[j] > count)
                        vec[j] = count;
                    count++;
                }
            }
        }
        return vec;
    }
};

1047 Remove All Adjacent Duplicates In String

题目描述

Given a string S of lowercase letters, a duplicate removal consists of choosing two adjacent and equal letters, and removing them.

We repeatedly make duplicate removals on S until we no longer can.

Return the final string after all such duplicate removals have been made. It is guaranteed the answer is unique.

题目解析

反复的删除给定字符串中两个相邻且相等的字符。
做的时候有一个问题就是不要调用S.erase()在原来字符串S上进行删除，因为在遍历中S.length()作为循环的遍历条件，运行过程会出现Runtime Error。
看到题目属于的类别是栈，相邻其实就是将栈顶的字符与字符串中未入栈的字符比较，如果相等，则弹出栈顶字符，否则压入字符串中被比较的字符。如果栈为空，就直接压入字符串中的字符。
还是对一些数据结构的特点不熟悉，无法快速的转化。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    string removeDuplicates(string S){
    string res;
    for(int i=0;i<S.length();i++){
        if(!res.empty() && res[res.size()-1] == S[i]){
                res.pop_back();
        }
        else
            res.push_back(S[i]);
        }
        return res;
    }
};

参考

https://leetcode.com/problems/remove-all-adjacent-duplicates-in-string/discuss/367583/C%2B%2B-Short-and-easy-to-understand

344 Reverse String

题目简述

Write a function that reverses a string. The input string is given as an array of characters char[].

Do not allocate extra space for another array, you must do this by modifying the input array in-place with O(1) extra memory.

You may assume all the characters consist of printable ascii characters.

题目解析

反转字符串，要求空间复杂度为O(1)。

1
2
3
4
5
6
7
8
9
10
11
class Solution {
public:
    void reverseString(vector<char>& s){
        for(int i=0;i<s.size()/2;i++){
            char temp = s[i];
            s[i] = s[s.size()-1-i];
            s[s.size()-1-i] = temp;
        }
        return;
    }
};

优化：直接调用swap函数进行两个字符的交换，关闭iostream的输入缓存。

1
2
ios::sync_with_stdio(false);
cin.tie(0);

待增加