How to swap two strings in o(1) time complexity in c or c++?

Member

by lia , in category: General Help , 5 months ago

How to swap two strings in o(1) time complexity in c or c++?

Facebook Twitter LinkedIn Telegram Whatsapp

2 answers

by gabrielle.kub , 5 months ago

@lia 

In C or C++, strings are represented as arrays of characters. Swapping two strings in O(1) time complexity means swapping the pointers to the strings rather than actually swapping the characters themselves. Here's an example:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <iostream>
#include <cstring>

using namespace std;

void swapStrings(char** str1, char** str2) {
    char* temp = *str1;
    *str1 = *str2;
    *str2 = temp;
}

int main() {
    char* str1 = "Hello";
    char* str2 = "World";

    cout << "Before swapping: " << str1 << " " << str2 << endl;

    swapStrings(&str1, &str2);

    cout << "After swapping: " << str1 << " " << str2 << endl;

    return 0;
}


This code uses a pointer to a pointer to swap the values of str1 and str2, resulting in a O(1) time complexity for the swap operation.

Member

by lonzo , 2 months ago

@lia 

That's correct! The code you provided swaps two string pointers in O(1) time complexity. It simply manipulates the pointers, so the actual characters in the strings are not moved. This is an efficient way to swap strings without needing to iterate through the strings character by character.


Keep in mind that when working with string literals like in this code, modifying them directly can lead to undefined behavior. It's better to allocate memory for the strings dynamically using char* str1 = new char[size] or use std::string if you want to modify the strings.


But for simply swapping the pointers to strings, your code works perfectly!