C++ String Representation

C++ supports text processing through two primary mechanisms: the traditional C-style character array and the standard std::string class introduced in the C++ Standard Library.

C-Style Strings

Originating from the C language, C-style strings are essentially one-dimensional arrays of characters terminated by a null character \0. The array size must accommodate the string content plus this terminating null character.

Initialization can be done explicitly:

char buffer[7] = {'H', 'e', 'l', 'l', 'o', '!', '\0'};

Alternatively, the compiler can automatically handle the null termination:

char message[] = "Hello!";

The std::string Class

The C++ Standard Library provides the std::string class, which encapsulates dynamic array management and offers a rich set of member functions for manipulation.

#include <iostream>
#include <string>

using namespace std;

int main() {
    string firstName = "John";
    string lastName = "Doe";
    string fullName;

    // Assignment
    fullName = firstName;
    cout << "Assigned: " << fullName << endl;

    // Concatenation
    fullName = firstName + " " + lastName;
    cout << "Full Name: " << fullName << endl;

    // Size calculation
    cout << "Length: " << fullName.length() << endl;

    return 0;
}

Function	Description	Usage
length / size	Returns the number of characters	str.length();
empty	Checks if the string has no characters	str.empty();
clear	Removes all contents	str.clear();
append	Adds characters to the end	str.append("xyz");
push_back	Adds a single character to the end	str.push_back('a');
insert	Inserts characters at a specific position	str.insert(0, "Start");
erase	Removes characters from a range	str.erase(0, 5);
substr	Extracts a substring	str.substr(0, 5);
find	Locates the first occurrence of a substring	str.find("key");
replace	Replaces a portion of the string	str.replace(0, 4, "New");
c_str	Returns a const C-style string pointer	str.c_str();
stoi	Converts string to integer	std::stoi("42");
to_string	Converts numerical value to string	std::to_string(42);

Common String Algorithms

Reverse String

Problem: Reverse a vector of characters in-place.

#include <vector>
#include <algorithm>

class Solution {
public:
    void reverseString(std::vector<char>& input) {
        int left = 0;
        int right = input.size() - 1;
        while (left < right) {
            std::swap(input[left], input[right]);
            left++;
            right--;
        }
    }
};

Reverse String II

Problem: Given a string and an integer k, reverse the first k characters for every 2k characters counting from the start. If fewer than k characters are left, reverse all of them.

#include <string>
#include <algorithm>

class Solution {
public:
    std::string reverseStr(std::string s, int k) {
        for (int idx = 0; idx < s.size(); idx += 2 * k) {
            int endIdx = std::min(idx + k, (int)s.size());
            std::reverse(s.begin() + idx, s.begin() + endIdx);
        }
        return s;
    }
};

Reverse Words in a String

Problem: Reverse the order of words in a string, removing extra whitespace.

#include <string>
#include <algorithm>

class Solution {
public:
    std::string reverseWords(std::string s) {
        int slow = 0;
        int fast = 0;
        int n = s.length();

        // Remove leading spaces
        while (fast < n && s[fast] == ' ') fast++;

        // Process internal spaces and characters
        while (fast < n) {
            if (s[fast] == ' ' && (fast + 1 < n && s[fast + 1] == ' ')) {
                fast++;
            } else {
                s[slow++] = s[fast++];
            }
        }

        // Remove trailing space if any
        if (slow > 0 && s[slow - 1] == ' ') {
            slow--;
        }
        s.resize(slow);

        // Reverse entire string
        std::reverse(s.begin(), s.end());

        // Reverse individual words
        int start = 0;
        for (int i = 0; i <= s.size(); ++i) {
            if (i == s.size() || s[i] == ' ') {
                std::reverse(s.begin() + start, s.begin() + i);
                start = i + 1;
            }
        }
        return s;
    }
};

Find the Index of the First Occurrence

Problem: Return the index of the first occurrence of needle in haystack, or -1 if needle is not part of haystack.

#include <string>

class Solution {
public:
    int strStr(std::string haystack, std::string needle) {
        int hLen = haystack.size();
        int nLen = needle.size();
        if (nLen == 0) return 0;
        if (hLen < nLen) return -1;

        for (int i = 0; i <= hLen - nLen; ++i) {
            int j = 0;
            for (; j < nLen; ++j) {
                if (haystack[i + j] != needle[j]) break;
            }
            if (j == nLen) return i;
        }
        return -1;
    }
};

Repeated Substring Pattern

Problem: Check if a string can be constructed by taking a substring of it and appending multiple copies of the substring together.

#include <string>

class Solution {
public:
    bool repeatedSubstringPattern(std::string s) {
        std::string doubled = s + s;
        // Remove the first and last character to avoid matching the original string immediately
        return doubled.find(s, 1) != s.size();
    }
};

Zigzag Conversion

Problem: Write the string in a zigzag pattern on a given number of rows and read line by line.

#include <string>
#include <vector>

class Solution {
public:
    std::string convert(std::string s, int numRows) {
        if (numRows <= 1) return s;
        std::vector<std::string> rows(numRows);
        int curRow = 0;
        int direction = 1; // 1 for down, -1 for up

        for (char c : s) {
            rows[curRow] += c;
            curRow += direction;
            if (curRow == 0 || curRow == numRows - 1) {
                direction *= -1;
            }
        }

        std::string result;
        for (const std::string& r : rows) {
            result += r;
        }
        return result;
    }
};

String to Integer (atoi)

Problem: Implement the myAtoi function which converts a string to a 32-bit signed integer.

#include <string>
#include <climits>

class Solution {
public:
    int myAtoi(std::string str) {
        int index = 0;
        int sign = 1;
        long result = 0;
        int len = str.length();

        // Skip whitespace
        while (index < len && str[index] == ' ') {
            index++;
        }
        if (index == len) return 0;

        // Handle sign
        if (str[index] == '-' || str[index] == '+') {
            sign = (str[index] == '-') ? -1 : 1;
            index++;
        }

        // Convert digits
        while (index < len && isdigit(str[index])) {
            int digit = str[index] - '0';
            result = result * 10 + digit;

            // Check for overflow
            if (sign == 1 && result > INT_MAX) return INT_MAX;
            if (sign == -1 && -result < INT_MIN) return INT_MIN;
            index++;
        }

        return (int)(sign * result);
    }
};

Regular Expression Matching

Problem: Given an input string s and a pattern p, implement regular expression matching with support for '.' and '*'.

#include <string>
#include <vector>

class Solution {
public:
    bool isMatch(std::string s, std::string p) {
        int m = s.size(), n = p.size();
        std::vector<std::vector<bool>> dp(m + 1, std::vector<bool>(n + 1, false));
        dp[0][0] = true;

        // Handle patterns like a*, a*b*, a*b*c*
        for (int j = 2; j <= n; j++) {
            if (p[j - 1] == '*') {
                dp[0][j] = dp[0][j - 2];
            }
        }

        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (p[j - 1] == '.' || p[j - 1] == s[i - 1]) {
                    dp[i][j] = dp[i - 1][j - 1];
                } else if (p[j - 1] == '*') {
                    // Treat '*' as zero occurrences of preceding char
                    dp[i][j] = dp[i][j - 2];
                    // Treat '*' as one or more occurrences
                    if (p[j - 2] == '.' || p[j - 2] == s[i - 1]) {
                        dp[i][j] = dp[i][j] || dp[i - 1][j];
                    }
                }
            }
        }
        return dp[m][n];
    }
};