Xin ý tưởng về bài tập chuỗi
Đề bài:
Given an array of strings, produce a single string as follows:
Repeat the following steps while there is more than one string in the array:
find the shortest string in the array (if there are several strings of the same length take the leftmost one);
find the shortest string among the rest (if there are several strings of the same length take the rightmost one);
extract the chosen strings from the array;
append the result of their concatenation (the second string should be added to the end of the first string) to the right end of the array.
After the algorithm has finished, there will be a single string left in the array. Return that string.
Đọc đề thì em hiểu sơ sơ nhưng khi xem ví dụ thì em thấy rối não quá mong mọi người cho em xin chút ý tưởng. Quên mất ví dụ của đề bài:
input: A = {“a”, “abc”, “abcc”, “aaa”, " ", “qw”, “z”};
output: A=“abc aaa abcc qw a z”
khó quá, mình cũng không hiểu nó là gì!
mình đọc đề thì hiểu sơ sơ nhưng nó cho cái ví dụ nên mình rối não quá, nghĩ mãi mà không ra
Thế này nhé.
Step 1: chuỗi ngắn nhất là “a”, phần còn lại là { “abc”, “abcc”, “aaa”, " “, “qw”, “z”}; phần ngắn nhất từ phải sang là “z”, loại “a” và “z” ra nối thành chuỗi “az”, thêm vào cuối mảng ta đc mảng mới là {“abc”, “abcc”, “aaa”, " “, “qw”, “az”};
Step 2: chuỗi ngắn nhất là " “, phần còn lại là { “abc”, “abcc”, “aaa”, “qw”, “az”}; phần ngắn nhất từ phải sang là “az”, loại " " và “az” ra nối thành chuỗi " az”, thêm vào cuối mảng ta đc mảng mới là {“abc”, “abcc”, “aaa”, “qw”, " az”};
Step 3: chuỗi ngắn nhất là “qw”, phần còn lại là { “abc”, “abcc”, “aaa”, " az”}; phần ngắn nhất từ phải sang là " az", loại “qw” và " az" ra nối thành chuỗi “qw az”, thêm vào cuối mảng ta đc mảng mới là {“abc”, “abcc”, “aaa”, “qw az”};
Step 4: chuỗi ngắn nhất là “abc”, phần còn lại là { “abcc”, “aaa”, “qw az”}; phần ngắn nhất từ phải sang là “aaa”, loại “abc” và “aaa” ra nối thành chuỗi “abcaaa”, thêm vào cuối mảng ta đc mảng mới là {“abcc”, “qw az”,“abcaaa”};
Step 5: chuỗi ngắn nhất là “abcc”, phần còn lại là { “qw az”, “abcaaa”}; phần ngắn nhất từ phải sang là “qw az”, loại “abcc” và “qw az” ra nối thành chuỗi “abccqw az”, thêm vào cuối mảng ta đc mảng mới là {“abcaaa”, “abccqw az”};
Step 6: Step 5: chuỗi ngắn nhất là “abcaaa”, phần còn lại là {“abccqw az”}; phần ngắn nhất từ phải sang là “abccqw az”, loại “abcaaa” và “abccqw az” ra nối thành chuỗi “abcaaaabccqw az”, thêm vào cuối mảng ta đc mảng mới là { “abcaaaabccqw az”};
Vậy đáp số là “abcaaaabccqw az”
Có vẻ đáp án chưa đúng! Mình nghĩ làm theo mình là đúng!
cám ơn bạn nhiều, tý nữa ra oai được với thằng bạn