Autocorrect algorithm - How to implement a decent "apostrophe & elision" feature?
You've asked two questions: about what algorithm can be used, and how it is implemented in Android.  Only the former is on-topic here, so I'll answer the former.  (Also, our guidelines are that you should generally ask only one question per post.)



Suppose French has the rule that the two words "X Y" are always replaced by an elided single-word replacement if X is one of ce, je, ne, me, te, se, le, la, de, que, or si and if Y starts with a vowel or silent "h".  I don't know French well enough to know if this is indeed the rule, so I'll assume that's how French works.

To suggest elisions, you could precompute a mini-dictionary of all words Y that start with a vowel or silent "h".  Then, it is easy to search all text entered to see whether it contains a pair of words of the form "X Y" where X is one of ce, je, ne, me, te, se, le, la, de, que, or si and Y is in the mini-dictionary.  If you find such a pair, then you can programmatically generate the correct elision and automatically suggest it.  This should be straightforward to implement.

Precomputing the mini-dictionary should be feasible.  It should be easy to find a dictionary of all valid French words and identify which ones start with a vowel and which ones start with an "h".  The trickiest bit is you'll need a way to identify all French words that start with a silent "h".  I don't know enough about French to know whether there's a clever way to do that.  However, a brute-force method is probably sufficient: I expect it would be sufficient to do it manually (list all words that start with a "h" and identify which have a silent "h"), or crowdsource it (something like Amazon Mechnical Turk, targeted at native French speakers).  This only needs to be done once, so generating the mini-dictionary should be feasible.



I'll also mention a complementary method that's probably also worth adopting.  Compute the list of all elisions, as above (by iterating over all valid pairs "X Y" that will trigger elision, then programmatically computing the correct elision).  Then, add each possible elided form listed above to your spelling dictionary.  In other words, extend your dictionary to include all valid elisions that can ever be encountered.  This may be a useful supplement to the method above, as it will help detect typos when people try to type in the elided form but make a small mistake.

These two methods are complementary.  In particular, if someone types the unelided form (e.g., "Ce est"), the first method above will auto-suggest correcting that to the elided form ("C'est").  And, if someone tries to type the elided form but makes a typo (e.g., "C'ext"), the second method will auto-suggest how to correct the typo ("C'est").  You can decide whether both of those problems are important to solve, or whether you only want to solve one of these two problems, and use that to determine which of these methods to implement.