DEV Community

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

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

1 1 1 1 1

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. 😊📁✨

Postmark Image

Speedy emails, satisfied customers

Are delayed transactional emails costing you user satisfaction? Postmark delivers your emails almost instantly, keeping your customers happy and connected.

Sign up

Top comments (0)

Billboard image

The Next Generation Developer Platform

Coherence is the first Platform-as-a-Service you can control. Unlike "black-box" platforms that are opinionated about the infra you can deploy, Coherence is powered by CNC, the open-source IaC framework, which offers limitless customization.

Learn more