SRM 149 Division-I, Level 2

Problem Statement

It is a common practice in cryptography to remove the spaces from a message before encoding it to help to disguise its structure. Even after it is then decoded, we are left with the problem of putting the spaces back in the message.
Create a class MessageMess that contains a method restore that takes a vector dictionary of possible words and a string message as inputs. It returns the message with single spaces inserted to divide the message into words from the dictionary. If there is more than one way to insert spaces, it returns "AMBIGUOUS!"If there is no way to insert spaces, it returns "IMPOSSIBLE!"The return should never have any leading or trailing spaces.
Definition

Class:
MessageMess
Method:
restore
Parameters:
vector , string
Returns:
string
Method signature:
string restore(vector dictionary, string message)
(be sure your method is public)

Notes
-
Don't forget the '!' at the end of the two special returns
-
A proper message may require 0 spaces to be inserted
Constraints
-
dictionary will contain between 1 and 50 elements inclusive
-
the elements of dictionary will be distinct
-
each element of dictionary will contain between 1 and 50 characters
-
message will contain between 1 and 50 characters
-
every character in message and in each element of dictionary will be an uppercase letter 'A'-'Z'
Examples
0)

{"HI", "YOU", "SAY"}
"HIYOUSAYHI"
Returns: "HI YOU SAY HI"
A word from dictionary may appear multiple times in the message.
1)

{"ABC", "BCD", "CD", "ABCB"}
"ABCBCD"
Returns: "AMBIGUOUS!"
"ABC BCD"and "ABCB CD"are both possible interpretations of message.
2)

{"IMPOSS", "SIBLE", "S"}
"IMPOSSIBLE"
Returns: "IMPOSSIBLE!"
There is no way to concatenate words from this dictionary to form "IMPOSSIBLE"
3)

{"IMPOSS", "SIBLE", "S", "IMPOSSIBLE"}
"IMPOSSIBLE"
Returns: "IMPOSSIBLE"
This message can be decoded without ambiguity. This requires the insertion of no spaces since the entire message appears as a word in the dictionary.
This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2003, TopCoder, Inc. All rights reserved.
This problem tripped a lot of people up, mostly because the examples made it look like a brute force approach might work. But, as experienced TopCoders will tell you, medium level problems usually aren't that simple. To solve this problem in time required a little bit of simple dynamic programming. You should have a String[] to keep track of valid restored substrings. That is, element i of the String[] represents a valid restoration of the characters from 0 to i, if there is one. If there is no valid restoration, or if there is more than one valid restoration, the String[] should have "IMPOSSIBLE!", or "AMBIGUOUS!", respectively. So, how do we do this now? Well, if there is a valid restoration for a substring, then there is a last word in that restoration. So, if we have a valid restoration for characters 0 to i, then we check each word to see if adding that word to the restoration from 0 to i is consistent with the input. If it is, then we update the restoration from 0 to j, where j is the index of the character where the added word ends. Once we have this figured out, its pretty simple to handle the cases where the return is "AMBIGUOUS!"or "IMPOSSIBLE!". I should note that another way to solve this problem is to use memoized recursion, which involves a recursive function that determines whether a substring from character 0 to character i can be restored or not. Here is dgoodman's (the writer) code:

 int len = mess.length(); 
 int[] ways = new int[len+1];
 String[] ans = new String[len+1]; 
 ways[0]=1;
 ans[0]="";
 for(int i=0; i<len; i++){
 if(ways[i]>0){
 for(int id = 0; id<dic.length; id++){
 String word = dic[id]; int n = i + word.length();
 if(n>len) continue; 
 if(!word.equals(mess.substring(i,n))) continue;
 if(ways[n]>0) ways[n]=2; else ways[n]=ways[i];
 if(ways[n]==1) ans[n] = ans[i] + " " + word;
 }
 }
 }
 if(ways[len]>1) return "AMBIGUOUS!";
 if(ways[len]<1) return "IMPOSSIBLE!";
 return ans[mess.length()].trim();

class MessageMess{ public: bool Match(string s1, string s2) { for (int i = 0; i < s1.size(); ++i) { if (s1[i] != s2[i])return false; } return true; } string restore(vector dictionary, string message) { vector rec; vector rlen; for (int i = 0; i < message.size(); ++i) for (int j = 0; j < dictionary.size(); ++j) { if (i == 0 && Match(dictionary[j], message)) { rec.push_back(dictionary[j]); rlen.push_back(dictionary[j].size()); continue; } for (int k = 0; k < rec.size(); ++k) { if (i == rlen[k] && Match(dictionary[j], message.substr(i))) { rlen[k] += dictionary[j].size(); rec[k] +=" " + dictionary[j]; } } }; int cnt = 0; int index = 0; for (int i = 0; i < rec.size(); ++i) if (rlen[i]== message.size())++cnt,index = i; if (cnt ==0)return "IMPOSSIBLE!"; else if (cnt > 1)return "AMBIGUOUS!"; return rec[index]; } };

이 내용에 흥미가 있습니까?

현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:

Send an email with well formatted excel as attachment

DATA: l_control TYPE REF TO i_oi_container_control, l_container TYPE REF TO cl_gui_custom_container, l_doc_signatures TY...

텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.

CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.

SRM 149 Division-I, Level 2

좋은 웹페이지 즐겨찾기