DailyCodingProblem/Hard_Prob226.cpp at main · Swendart/DailyCodingProblem · GitHub

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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
/* ou come across a dictionary of sorted words in a language you've never seen before. Write a program that returns the correct order of letters in this language.

For example, given ['xww', 'wxyz', 'wxyw', 'ywx', 'ywz'], you should return ['x', 'z', 'w', 'y'].*/

#include <iostream>
#include <vector>
#include <cmath>
#include<bits/stdc++.h>

using namespace std;

vector<char> orderLetter(vector<string> sortedWords) {
    int numbersWords = sortedWords.size();

    vector<char> sortedLetters ;

    for (int i=0; i<numbersWords-1; i++) {
        int j = i+1;
            if (i != j) {
                string word1 = sortedWords[i];
                string word2 = sortedWords[j];

                // Find difference character between 2 words
                int index = 0;
                bool notDiff = index<word1.size() && index<word2.size() && word1[i] == word2[i];
                while (notDiff) {
                    index ++;
                    notDiff = index<word1.size() && index<word2.size() && word1[index] == word2[index];
                }

                // cout << word1[index] << " " << word2[index] << endl;

                // Adjust order in
                if (index >= word1.size()) {
                    // cout << "Inutile" << endl;
                } else {
                    // Find if word1[index] is already in sortedLetters
                    bool char1isIn = false;
                    for (char c : sortedLetters) {
                        if (word1[index] == c) {
                            char1isIn = true;
                            break;
                        }
                    }

                    // Find if word2[index] is already in sortedLetters
                    bool char2isIn = false;
                    for (char c : sortedLetters) {
                        if (word2[index] == c) {
                            char2isIn = true;
                            break;
                        }
                    }

                    if (char1isIn && char2isIn) {
                        // Verify is char1 is before char2
                        vector<char>::iterator char1Index = sortedLetters.begin();
                        vector<char>::iterator char2Index = sortedLetters.begin();

                        for (vector<char>::iterator k=sortedLetters.begin(); k<sortedLetters.end(); k++) {
                            if (*k == word1[index]) {
                                char1Index = k;
                            } else if (*k == word1[index]) {
                                char2Index = k;
                            }
                        }

                        if (char1Index > char2Index) {
                            sortedLetters.erase(char1Index);
                            sortedLetters.insert(char2Index,word1[index]);
                        }
                    } else if (char1isIn && !char2isIn) {
                        // Find index of char2
                        vector<char>::iterator char1Index = sortedLetters.begin();
                        for (vector<char>::iterator k=sortedLetters.begin(); k<sortedLetters.end(); k++) {
                            if (*k == word1[index]) {
                                char1Index = k;
                                break;
                            }
                        }

                        sortedLetters.insert(char1Index+1, word2[index]);
                    } else if (!char1isIn && char2isIn) {
                        // Find index of char2
                        vector<char>::iterator char2Index = sortedLetters.begin();
                        for (vector<char>::iterator k=sortedLetters.begin(); k<sortedLetters.end(); k++) {
                            if (*k == word2[index]) {
                                char2Index = k;
                                break;
                            }
                        }

                        sortedLetters.insert(char2Index, word1[index]);

                    } else {
                        sortedLetters.push_back(word1[index]);
                        sortedLetters.push_back(word2[index]);
                    }

                }

            }
    }
    return sortedLetters;
}

int main(int argc, char *argv[])
{
    vector<string> sortedWords = {"xvw", "xvwy", "wxyz", "wxyw", "ywx"};
    vector<char> order = orderLetter(sortedWords);

    for (int i=0; i<order.size(); i++) {
        cout << order[i] << " " ;
    }

    cout << "\n";
}