Decoding Morse Sequences - POJ 1432


http://poj.org/problem?id=1432
Before the digital age, the most common "binary" code for radio communication was the Morse code. In Morse code, symbols are encoded as sequences of short and long pulses (called dots and dashes respectively). The following table reproduces the Morse code for the alphabet, where dots and dashes are represented as ASCII characters "." and "-":

Notice that in the absence of pauses between letters there might be multiple interpretations of a Morse sequence. For example, the sequence -.-..-- could be decoded both as CAT or NXT (among others). A human Morse operator would use other context information (such as a language dictionary) to decide the appropriate decoding. But even provided with such dictionary one can obtain multiple phrases from a single Morse sequence.


Task

Write a program which for each data set:

reads a Morse sequence and a list of words (a dictionary),

computes the number of distinct phrases that can be obtained from the given Morse sequence using words from the dictionary,

writes the result.

Notice that we are interested in full matches, i.e. the complete Morse sequence must be matched to words in the dictionary.
Input
The first line of the input contains exactly one positive integer d equal to the number of data sets, 1 <= d <= 20. The data sets follow.

The first line of each data set contains a Morse sequence - a nonempty sequence of at most 10 000 characters "." and "-" with no spaces in between.

The second line contains exactly one integer n, 1 <= n <= 10 000, equal to the number of words in a dictionary. Each of the following n lines contains one dictionary word - a nonempty sequence of at most 20 capital letters from "A" to "Z". No word occurs in the dictionary more than once. 
Output
The output should consist of exactly d lines, one line for each data set. Line i should contain one integer equal to the number of distinct phrases into which the Morse sequence from the i-th data set can be parsed. You may assume that this number is at most 2 * 10^9 for every single data set.
Sample Input
1
.---.--.-.-.-.---...-.---.
6
AT
TACK
TICK
ATTACK
DAWN
DUSK
Sample Output
2
http://java-mans.iteye.com/blog/1647991
计算一段文摩斯码可能的译文种数,定义dp[i]为前i个摩斯码的种数,然后枚举最后一个单词的摩斯码长度,将所有可能加起来;要注意的是有些单词的摩斯码相同。

http://www.acmerblog.com/hdu-1523-Decoding-Morse-Sequences-2080.html
23string rec;
24char s[10100],str[10100];
25int dp[10100];
26int len;
27char cod[26][5]={
28            ".-","-...","-.-.","-..",
29            ".","..-.","--.","....",
30            "..",".---","-.-",".-..",
31            "--","-.","---",".--.",
32            "--.-",".-.","...","-",
33            "..-","...-",".--","-..-",
34            "-.--","--.."
35            };
36map<string ,int>mp;
37int main()
38{
39    int t,n,i,j,k;
40    scanf("%d",&t);
41   // getchar();
42 //   cout<<cod[0];
43    while(t--)
44    {
45        mp.clear();
46        memset(dp,0,sizeof(dp));
47       scanf("%s",s+1);
48       len=strlen(s+1);
49   //    printf("len %d\n",len);
50       scanf("%d",&n);
51       for(i=0;i<n;i++)
52       {
53            scanf("%s",str);
54          //  int len=strlen(str);
55            string tmp;
56            for(j=0;str[j];j++)
57                tmp+=cod[str[j]-'A'];
58           // cout<<tmp<<endl;
59            mp[tmp]++;
60       }
61       dp[0]=1;
62       for(i=1;i<=len;i++)
63            for(j=i-1;j>=i-81&&j>=0;j--)
64            {
65                if(dp[j]==0)
66                    continue;
67                char a[100];
68                for(k=j+1;k<=i;k++)
69                {
70                    a[k-j-1]=s[k];
71                }
72                a[k-j-1]=0;
73 
74                  //  cout<<a<<endl;
75                    dp[i]+=dp[j]*mp[a];
76              //  printf("i %d dp %d\n",i,dp[i]);
77            }
78        printf("%d\n",dp[len]);
79    }
http://blog.csdn.net/program_shun/article/details/6581420
首先编码只有-和.,可以很方便地建立一棵Trie树,还是最熟悉的二叉方式。
typedef struct trie
{
    int count;                  //单词数 
    struct trie *dot, *dash;    
}trie;

之后将每一个读入的单词插到Trie树上。
 用动态规划处理 Morse sequence, 下面记为str。
记f[i]为第i个字符到strlen(str)-1的不同解码数,f[i]=sum(f[i+j]*count[k], 表示从i开始的j位可以解码为一个单词,且相同编码的单词有count[k]个),具体的count和单词的匹配用之前建立的Trie树完成。

const char* morse[26] = {
".-",   "-...", "-.-.", "-..",
".",    "..-.", "--.",  "....",
"..",   ".---", "-.-",  ".-..",
"--",   "-.",   "---",  ".--.",
"--.-", ".-.",  "...",  "-",
"..-",  "...-", ".--",  "-..-",
"-.--", "--.."
};   

typedef struct trie
{
    int count;                  //单词数 
    struct trie *dot, *dash;    
}trie;

trie *trie_new()
{
    trie *t = (trie *)malloc(sizeof(trie));
    t->dot = t->dash = NULL;
    t->count = 0;
    return t;
}

void trie_add(trie *root, const char code[])
{
    int p=0, len=strlen(code);
    trie *node=root;
    while (p<len)
    {
        if (code[p]=='.')
        {
            if (!node->dot)
                node->dot = trie_new();
            node = node->dot;
        }
        else
        {
            if (!node->dash)
                node->dash = trie_new();
            node = node->dash;
        }
        p++;
    }
    node->count++;
}

void trie_free(trie *p)
{
    if (p)
    {
        trie_free(p->dot);
        trie_free(p->dash);
        free(p);
    }
}

void getmorse(const char word[], char code[])
{
    int j=0;
    for (int i=0; i<strlen(word); i++)
    {
        int mlen=strlen(morse[word[i]-'A']); 
        for (int k=0; k<mlen; k++, j++)
            code[j]=morse[word[i]-'A'][k];
    }
    code[j]='\0';
}

void init(char str[], trie *root)
{
    int n;
    char word[maxlen], code[maxlen];
    scanf("%s", str);
    scanf("%d", &n);
    for (int i=0; i<n; i++)
    {
        scanf("%s", word);
        getmorse(word, code);
        trie_add(root, code);
    }
}

int dp(const char str[], trie *root)
{
    int f[maxn];
    int slen=strlen(str);
    f[slen]=1;
    for (int i=slen-1; i>=0; i--)
    {
        f[i]=0;
        trie *p=root;
        for (int j=i; j<slen; j++)
        {
            if (str[j]=='.')
            {
                if (p->dot==NULL) break;
                p=p->dot;
            }
            else
            {
                if (p->dash==NULL) break;
                p=p->dash;
            }
            if (p->count!=0) f[i] += (p->count)*f[j+1];
        }
    }
    return f[0];
}
https://github.com/zherebjatjew/morse/blob/master/src/com/android/dj/morse/Decoder.java
http://java-mans.iteye.com/blog/1647991
http://blog.csdn.net/xiaokui_wingfly/article/details/16840377
http://www.1point3acres.com/bbs/thread-148857-1-1.html
4. 简单说就是摩斯码。真心记不太清了。刚吃完饭,面试官很好说热身一下,先给个单词,然后给每个字母的摩斯码,然后产生出来这个单词的摩斯码。然后反过来,给个摩斯码,同样给出每个字母所对应的摩斯码,给出所有可能得单词。刷好LC就行了。有个很像的题。然后注意分析复杂度。

Labels

LeetCode (1432) GeeksforGeeks (1122) LeetCode - Review (1067) Review (882) Algorithm (668) to-do (609) Classic Algorithm (270) Google Interview (237) Classic Interview (222) Dynamic Programming (220) DP (186) Bit Algorithms (145) POJ (141) Math (137) Tree (132) LeetCode - Phone (129) EPI (122) Cracking Coding Interview (119) DFS (115) Difficult Algorithm (115) Lintcode (115) Different Solutions (110) Smart Algorithm (104) Binary Search (96) BFS (91) HackerRank (90) Binary Tree (86) Hard (79) Two Pointers (78) Stack (76) Company-Facebook (75) BST (72) Graph Algorithm (72) Time Complexity (69) Greedy Algorithm (68) Interval (63) Company - Google (62) Geometry Algorithm (61) Interview Corner (61) LeetCode - Extended (61) Union-Find (60) Trie (58) Advanced Data Structure (56) List (56) Priority Queue (53) Codility (52) ComProGuide (50) LeetCode Hard (50) Matrix (50) Bisection (48) Segment Tree (48) Sliding Window (48) USACO (46) Space Optimization (45) Company-Airbnb (41) Greedy (41) Mathematical Algorithm (41) Tree - Post-Order (41) ACM-ICPC (40) Algorithm Interview (40) Data Structure Design (40) Graph (40) Backtracking (39) Data Structure (39) Jobdu (39) Random (39) Codeforces (38) Knapsack (38) LeetCode - DP (38) Recursive Algorithm (38) String Algorithm (38) TopCoder (38) Sort (37) Introduction to Algorithms (36) Pre-Sort (36) Beauty of Programming (35) Must Known (34) Binary Search Tree (33) Follow Up (33) prismoskills (33) Palindrome (32) Permutation (31) Array (30) Google Code Jam (30) HDU (30) Array O(N) (29) Logic Thinking (29) Monotonic Stack (29) Puzzles (29) Code - Detail (27) Company-Zenefits (27) Microsoft 100 - July (27) Queue (27) Binary Indexed Trees (26) TreeMap (26) to-do-must (26) 1point3acres (25) GeeksQuiz (25) Merge Sort (25) Reverse Thinking (25) hihocoder (25) Company - LinkedIn (24) Hash (24) High Frequency (24) Summary (24) Divide and Conquer (23) Proof (23) Game Theory (22) Topological Sort (22) Lintcode - Review (21) Tree - Modification (21) Algorithm Game (20) CareerCup (20) Company - Twitter (20) DFS + Review (20) DP - Relation (20) Brain Teaser (19) DP - Tree (19) Left and Right Array (19) O(N) (19) Sweep Line (19) UVA (19) DP - Bit Masking (18) LeetCode - Thinking (18) KMP (17) LeetCode - TODO (17) Probabilities (17) Simulation (17) String Search (17) Codercareer (16) Company-Uber (16) Iterator (16) Number (16) O(1) Space (16) Shortest Path (16) itint5 (16) DFS+Cache (15) Dijkstra (15) Euclidean GCD (15) Heap (15) LeetCode - Hard (15) Majority (15) Number Theory (15) Rolling Hash (15) Tree Traversal (15) Brute Force (14) Bucket Sort (14) DP - Knapsack (14) DP - Probability (14) Difficult (14) Fast Power Algorithm (14) Pattern (14) Prefix Sum (14) TreeSet (14) Algorithm Videos (13) Amazon Interview (13) Basic Algorithm (13) Codechef (13) Combination (13) Computational Geometry (13) DP - Digit (13) LCA (13) LeetCode - DFS (13) Linked List (13) Long Increasing Sequence(LIS) (13) Math-Divisible (13) Reservoir Sampling (13) mitbbs (13) Algorithm - How To (12) Company - Microsoft (12) DP - Interval (12) DP - Multiple Relation (12) DP - Relation Optimization (12) LeetCode - Classic (12) Level Order Traversal (12) Prime (12) Pruning (12) Reconstruct Tree (12) Thinking (12) X Sum (12) AOJ (11) Bit Mask (11) Company-Snapchat (11) DP - Space Optimization (11) Dequeue (11) Graph DFS (11) MinMax (11) Miscs (11) Princeton (11) Quick Sort (11) Stack - Tree (11) 尺取法 (11) 挑战程序设计竞赛 (11) Coin Change (10) DFS+Backtracking (10) Facebook Hacker Cup (10) Fast Slow Pointers (10) HackerRank Easy (10) Interval Tree (10) Limited Range (10) Matrix - Traverse (10) Monotone Queue (10) SPOJ (10) Starting Point (10) States (10) Stock (10) Theory (10) Tutorialhorizon (10) Kadane - Extended (9) Mathblog (9) Max-Min Flow (9) Maze (9) Median (9) O(32N) (9) Quick Select (9) Stack Overflow (9) System Design (9) Tree - Conversion (9) Use XOR (9) Book Notes (8) Company-Amazon (8) DFS+BFS (8) DP - States (8) Expression (8) Longest Common Subsequence(LCS) (8) One Pass (8) Quadtrees (8) Traversal Once (8) Trie - Suffix (8) 穷竭搜索 (8) Algorithm Problem List (7) All Sub (7) Catalan Number (7) Cycle (7) DP - Cases (7) Facebook Interview (7) Fibonacci Numbers (7) Flood fill (7) Game Nim (7) Graph BFS (7) HackerRank Difficult (7) Hackerearth (7) Inversion (7) Kadane’s Algorithm (7) Manacher (7) Morris Traversal (7) Multiple Data Structures (7) Normalized Key (7) O(XN) (7) Radix Sort (7) Recursion (7) Sampling (7) Suffix Array (7) Tech-Queries (7) Tree - Serialization (7) Tree DP (7) Trie - Bit (7) 蓝桥杯 (7) Algorithm - Brain Teaser (6) BFS - Priority Queue (6) BFS - Unusual (6) Classic Data Structure Impl (6) DP - 2D (6) DP - Monotone Queue (6) DP - Unusual (6) DP-Space Optimization (6) Dutch Flag (6) How To (6) Interviewstreet (6) Knapsack - MultiplePack (6) Local MinMax (6) MST (6) Minimum Spanning Tree (6) Number - Reach (6) Parentheses (6) Pre-Sum (6) Probability (6) Programming Pearls (6) Rabin-Karp (6) Reverse (6) Scan from right (6) Schedule (6) Stream (6) Subset Sum (6) TSP (6) Xpost (6) n00tc0d3r (6) reddit (6) AI (5) Abbreviation (5) Anagram (5) Art Of Programming-July (5) Assumption (5) Bellman Ford (5) Big Data (5) Code - Solid (5) Code Kata (5) Codility-lessons (5) Coding (5) Company - WMware (5) Convex Hull (5) Crazyforcode (5) DFS - Multiple (5) DFS+DP (5) DP - Multi-Dimension (5) DP-Multiple Relation (5) Eulerian Cycle (5) Graph - Unusual (5) Graph Cycle (5) Hash Strategy (5) Immutability (5) Java (5) LogN (5) Manhattan Distance (5) Matrix Chain Multiplication (5) N Queens (5) Pre-Sort: Index (5) Quick Partition (5) Quora (5) Randomized Algorithms (5) Resources (5) Robot (5) SPFA(Shortest Path Faster Algorithm) (5) Shuffle (5) Sieve of Eratosthenes (5) Strongly Connected Components (5) Subarray Sum (5) Sudoku (5) Suffix Tree (5) Swap (5) Threaded (5) Tree - Creation (5) Warshall Floyd (5) Word Search (5) jiuzhang (5)

Popular Posts