DEV Community

Cover image for String for CP (DSA - 3)
Madhav Ganesan
Madhav Ganesan

Posted on • Updated on • Originally published at madhavganesan.hashnode.dev

String for CP (DSA - 3)

All basic data structures

Arrays
Dynamic Arrays (ArrayLists or Vectors)
Multidimensional Arrays

Linked Lists
Doubly Linked List
Circular Linked List

Stacks
Call Stack

Queues
Priority Queue
Deque (Double-ended Queue)
Circular Queue

Hash Tables / Hash map
LRU Cache (Least Recently Used)
Bloom Filter
Dictionary (python)

Trees
Red-Black Tree
AVL Tree
Segment Tree

Graphs
Adjacency List/Matrix
Minimum Spanning Tree (MST)
Disjoint Set (Union-Find)

Tries (Prefix Trees)
Radix Tree

Sets
Bit Set

Matrices
Sparse Matrix
Adjacency Matrix
Dynamic Programming Tables

Automatic removal of trailing and leading spaces in a string:

stringstream data structure handles the removal of trailing and leading spaces automatically

#include <sstream>
using namespace std;

void func(string s){

stringstream ss(s);
vector<string> words;

//read each word from the sentence
while(ss >> word){
words.push_back(word);
}

string str = "23,4,56";
stringstream ss(str);
string token;

while (getline(ss, token, ',')) {
    cout<<token<<endl;
}

}
Enter fullscreen mode Exit fullscreen mode

Convert char to integer:

int digit = num[i] - '0';
Enter fullscreen mode Exit fullscreen mode

Convert string to integer:

#include <iostream>
#include <string>
using namespace std;

int main() {
    string str = "12345";
    int num = stoi(str);
    return 0;
}
Enter fullscreen mode Exit fullscreen mode

Substring extraction:

num.substr(0,i+1);
//Parameters are starting_index,length
Enter fullscreen mode Exit fullscreen mode

4)Reverse Scan:
Iterating from last to first index of the string

5)Find substring present in target string:

#include <iostream>
#include <string>
using namespace std;

int main() {
    string str = "hello world";
    string target = "world";

    // Find the target substring in the string
    size_t position = str.find(target);

    // Check if the target substring was found
    if (position != string::npos) {
        cout << "Found '" << target << "' at position " << position << endl;
    } else {
        cout << "Substring not found" << endl;
    }

    return 0;
}

Enter fullscreen mode Exit fullscreen mode

std::string::npos is defined as the maximum value representable by size_t. This ensures it is out of the range of any valid index.

Functions that search within strings (like find, rfind, find_first_of, etc.) return std::string::npos if the substring or character is not found.

string::npos

Constant value used to indicate the failure of a search operation in strings.Typically defined as the maximum value of size_t.

size_t:

Special unsigned integer type used to represent sizes.
Can only hold non-negative values.

Sort function:

The sort function is used to order elements within a specified range. It is implemented using a highly optimized version of quicksort, mergesort, or heapsort, depending on the standard library implementation.

#include <iostream>
#include <vector>
#include <algorithm>  //for sort function
#include <functional> //for greater function
using namespace std;

bool descending(int a, int b) {
    return a > b;
}

bool compare(const pair<int, char>& a, const pair<int, char>& b) {
    return a.second > b.second;
}

int main() {
    vector<int> vec = {1, 3, 2, 5, 4};


    // Sort the vector in descending order using custom function
    sort(vec.begin(), vec.end(), descending);

    // Sort the vector in descending order using greater function
    sort(vec.begin(), vec.end(), greater<int>());

    vector<pair<int, char>> vec = {
        {1, 'a'},
        {3, 'c'},
        {2, 'b'},
        {4, 'd'}
    };

    //Sort in descending order for pair
    sort(vec.begin(), vec.end(), compare);

    return 0;
}
Enter fullscreen mode Exit fullscreen mode

Find function:

#include <iostream>
#include <unordered_map>
using namespace std;

int main() {
    unordered_map<string, int> one;
    one["apple"] = 1;
    one["banana"] = 2;
    one["cherry"] = 3;

    // Check if the key "banana" exists in the map
    if (one.find("banana") != one.end()) {
        cout << "\"banana\" found in the map.";
    } else {
        cout << "\"banana\" not found in the map.";
    }

    return 0;
}
Enter fullscreen mode Exit fullscreen mode

Check whether character or number or both:

#include <iostream>
#include <cctype>

int main() {
    char c = 'A';
    if (isalpha(c)) {
        cout<<"Alphabet";
    } else if (isalnum(c){
        cout<<"Alphanumeric";
    }
    return 0;
}
Enter fullscreen mode Exit fullscreen mode

Feel free to reach out if you have any questions or need further assistance. 😊📁✨

Top comments (0)